Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1042.html
1042. Flower Planting With No Adjacent (Easy)
You have N
gardens, labelled 1
to N
. In each garden, you want to plant one of 4 types of flowers.
paths[i] = [x, y]
describes the existence of a bidirectional path from garden x
to garden y
.
Also, there is no garden that has more than 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]
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]
Note:
1 <= N <= 10000
0 <= paths.size <= 20000
- No garden has 4 or more paths coming into or leaving it.
- It is guaranteed an answer exists.
Related Topics:
Graph
Solution 1.
-
class Solution { public int[] gardenNoAdj(int N, int[][] paths) { int[] flowers = new int[N]; Map<Integer, List<Integer>> adjacentMap = new HashMap<Integer, List<Integer>>(); for (int[] path : paths) { int garden1 = path[0] - 1, garden2 = path[1] - 1; List<Integer> pathList1 = adjacentMap.getOrDefault(garden1, new ArrayList<Integer>()); pathList1.add(garden2); adjacentMap.put(garden1, pathList1); List<Integer> pathList2 = adjacentMap.getOrDefault(garden2, new ArrayList<Integer>()); pathList2.add(garden1); adjacentMap.put(garden2, pathList2); } flowers[0] = 1; for (int i = 1; i < N; i++) { List<Integer> adjacent = adjacentMap.getOrDefault(i, new ArrayList<Integer>()); boolean[] used = new boolean[5]; for (int garden : adjacent) { int flower = flowers[garden]; if (flower > 0) used[flower] = true; } for (int j = 1; j < 5; j++) { if (!used[j]) { flowers[i] = j; break; } } } return flowers; } } ############ class Solution { public int[] gardenNoAdj(int n, int[][] paths) { List<Integer>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (int[] p : paths) { int x = p[0] - 1, y = p[1] - 1; g[x].add(y); g[y].add(x); } int[] ans = new int[n]; for (int u = 0; u < n; ++u) { Set<Integer> colors = new HashSet<>(); for (int v : g[u]) { colors.add(ans[v]); } for (int c = 1; c < 5; ++c) { if (!colors.contains(c)) { ans[u] = c; break; } } } return ans; } }
-
// OJ: https://leetcode.com/problems/flower-planting-with-no-adjacent/ // Time: O(N) // Space: O(N) class Solution { public: vector<int> gardenNoAdj(int N, vector<vector<int>>& paths) { vector<vector<int>> G(N); for (auto & e : paths) { G[e[0] - 1].push_back(e[1] - 1); G[e[1] - 1].push_back(e[0] - 1); } vector<int> ans(N); for (int i = 0; i < N; ++i) { int color[5] = {}; for (int j : G[i]) color[ans[j]] = 1; for (int j = 4; j > 0; --j) { if (color[j]) continue; ans[i] = j; break; } } return ans; } };
-
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 u in range(n): colors = set(ans[v] for v in g[u]) for c in range(1, 5): if c not in colors: ans[u] = c break return ans ############ class Solution(object): def gardenNoAdj(self, N, paths): """ :type N: int :type paths: List[List[int]] :rtype: List[int] """ res = [0] * N graph = [[] for i in range(N)] for path in paths: graph[path[0] - 1].append(path[1] - 1) graph[path[1] - 1].append(path[0] - 1) for i in range(N): neighbor_colors = [] for neighbor in graph[i]: neighbor_colors.append(res[neighbor]) for color in range(1, 5): if color in neighbor_colors: continue res[i] = color break return res
-
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 u := 0; u < n; u++ { colors := make(map[int]bool) for _, v := range g[u] { colors[ans[v]] = true } for c := 1; c < 5; c++ { if !colors[c] { ans[u] = c break } } } return ans }
-
function gardenNoAdj(n: number, paths: number[][]): number[] { const g: number[][] = new Array(n).fill(0).map(() => []); for (const [x, y] of paths) { g[x - 1].push(y - 1); g[y - 1].push(x - 1); } const ans: number[] = new Array(n).fill(0); for (let x = 0; x < n; ++x) { const used: boolean[] = new 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; }