1042. Flower Planting With No Adjacent

Description

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. 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 <= 104
• 0 <= paths.length <= 2 * 104
• paths[i].length == 2
• 1 <= xi, yi <= n
• xi != yi
• Every garden has at most 3 paths coming into or leaving it.

Solutions

Solution 1: Enumeration

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
    }
}

Comments