LeetCode 1042. Flower Planting With No Adjacent Solution in Java, C++, Python & More | Explanation + Code

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

PythonJavaC++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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)