1042. Flower Planting With No Adjacent

Description

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [x_i, y_i] describes a bidirectional path between garden x_i to garden y_i. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)^th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
Explanation:
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].

Example 2:

Input: n = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Constraints:

1 <= n <= 10⁴
0 <= paths.length <= 2 * 10⁴
paths[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
Every garden has at most 3 paths coming into or leaving it.

Solutions

Solution 1: Enumeration

Thinking

Degree is at most three and there are four colors, so a greedy coloring works and backtracking is unnecessary.

Build the adjacency list. For garden \(x\) collect colors already used by neighbors and assign the first free color in \(1..4\).

A vertex of degree \(\le 3\) always has a free color; one pass finishes.

We first construct a graph \(g\) based on the array \(\textit{paths}\), where \(g[x]\) represents the list of gardens adjacent to garden \(x\).

Next, for each garden \(x\), we first find the gardens \(y\) adjacent to \(x\) and mark the types of flowers planted in garden \(y\) as used. Then, we enumerate the flower types starting from \(1\) until we find a flower type \(c\) that has not been used. We assign \(c\) as the flower type for garden \(x\) and continue to the next garden.

After the enumeration is complete, we return the result.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\), where \(n\) is the number of gardens and \(m\) is the number of paths.

Python3JavaC++GoTypeScriptRust

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        g = defaultdict(list)
        for x, y in paths:
            x, y = x - 1, y - 1
            g[x].append(y)
            g[y].append(x)
        ans = [0] * n
        for x in range(n):
            used = {ans[y] for y in g[x]}
            for c in range(1, 5):
                if c not in used:
                    ans[x] = c
                    break
        return ans

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var p : paths) {
            int x = p[0] - 1, y = p[1] - 1;
            g[x].add(y);
            g[y].add(x);
        }
        int[] ans = new int[n];
        boolean[] used = new boolean[5];
        for (int x = 0; x < n; ++x) {
            Arrays.fill(used, false);
            for (int y : g[x]) {
                used[ans[y]] = true;
            }
            for (int c = 1; c < 5; ++c) {
                if (!used[c]) {
                    ans[x] = c;
                    break;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> g(n);
        for (auto& p : paths) {
            int x = p[0] - 1, y = p[1] - 1;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        vector<int> ans(n);
        bool used[5];
        for (int x = 0; x < n; ++x) {
            memset(used, false, sizeof(used));
            for (int y : g[x]) {
                used[ans[y]] = true;
            }
            for (int c = 1; c < 5; ++c) {
                if (!used[c]) {
                    ans[x] = c;
                    break;
                }
            }
        }
        return ans;
    }
};

func gardenNoAdj(n int, paths [][]int) []int {
    g := make([][]int, n)
    for _, p := range paths {
        x, y := p[0]-1, p[1]-1
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }
    ans := make([]int, n)
    for x := 0; x < n; x++ {
        used := [5]bool{}
        for _, y := range g[x] {
            used[ans[y]] = true
        }
        for c := 1; c < 5; c++ {
            if !used[c] {
                ans[x] = c
                break
            }
        }
    }
    return ans
}

function gardenNoAdj(n: number, paths: number[][]): number[] {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [x, y] of paths) {
        g[x - 1].push(y - 1);
        g[y - 1].push(x - 1);
    }
    const ans: number[] = Array(n).fill(0);
    for (let x = 0; x < n; ++x) {
        const used: boolean[] = Array(5).fill(false);
        for (const y of g[x]) {
            used[ans[y]] = true;
        }
        for (let c = 1; c < 5; ++c) {
            if (!used[c]) {
                ans[x] = c;
                break;
            }
        }
    }
    return ans;
}

impl Solution {
    pub fn garden_no_adj(n: i32, paths: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut g = vec![vec![]; n];

        for path in paths {
            let (x, y) = (path[0] as usize - 1, path[1] as usize - 1);
            g[x].push(y);
            g[y].push(x);
        }

        let mut ans = vec![0; n];
        for x in 0..n {
            let mut used = [false; 5];
            for &y in &g[x] {
                used[ans[y] as usize] = true;
            }
            for c in 1..5 {
                if !used[c] {
                    ans[x] = c as i32;
                    break;
                }
            }
        }
        ans
    }
}

1042. Flower Planting With No Adjacent

Description

Solutions

Solution 1: Enumeration

Comments