# 1042. Flower Planting With No Adjacent

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: vector gardenNoAdj(int n, vector>& paths) { vector ans(n); // ans[i] := 1, 2, 3, or 4 vector> graph(n); for (const auto& p : paths) { const int u = p[0] - 1; const int v = p[1] - 1; graph[u].push_back(v); graph[v].push_back(u); } for (int i = 0; i < n; ++i) { vector used(5); for (const int v : graph[i]) used[ans[v]] = true; for (int type = 1; type < 5; ++type) if (!used[type]) { ans[i] = type; break; } } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public int[] gardenNoAdj(int n, int[][] paths) { int[] ans = new int[n]; // ans[i] := 1, 2, 3, or 4 List[] graph = new List[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] p : paths) { final int u = p[0] - 1; final int v = p[1] - 1; graph[u].add(v); graph[v].add(u); } for (int i = 0; i < n; ++i) { boolean[] used = new boolean[5]; for (final int v : graph[i]) used[ans[v]] = true; for (int type = 1; type < 5; ++type) if (!used[type]) { ans[i] = type; break; } } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]: ans = [0] * n # ans[i] := 1, 2, 3, or 4 graph = [[] for _ in range(n)] for a, b in paths: u = a - 1 v = b - 1 graph[u].append(v) graph[v].append(u) for i in range(n): used = [False] * 5 for v in graph[i]: used[ans[v]] = True for type in range(1, 5): if not used[type]: ans[i] = type break return ans