Flower Planting With No Adjacent
Problem
You have n gardens labelled 1..n and bidirectional paths joining some of them; every garden has at most 3 paths. You have 4 flower types (1..4). Plant one flower type per garden so that no two gardens joined by a path share the same type. Return any valid assignment as an array answer where answer[i] is the type planted in garden i+1.
n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3]][1, 2, 3, 4]def gardenNoAdj(n, paths):
adj = [[] for _ in range(n)]
for a, b in paths:
adj[a - 1].append(b - 1)
adj[b - 1].append(a - 1)
answer = [0] * n
for g in range(n):
used = {answer[h] for h in adj[g]}
for c in (1, 2, 3, 4):
if c not in used:
answer[g] = c
break
return answerfunction gardenNoAdj(n, paths) {
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of paths) {
adj[a - 1].push(b - 1);
adj[b - 1].push(a - 1);
}
const answer = new Array(n).fill(0);
for (let g = 0; g < n; g++) {
const used = new Set(adj[g].map(h => answer[h]));
for (let c = 1; c <= 4; c++) {
if (!used.has(c)) { answer[g] = c; break; }
}
}
return answer;
}class Solution {
public int[] gardenNoAdj(int n, int[][] paths) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] p : paths) {
adj.get(p[0] - 1).add(p[1] - 1);
adj.get(p[1] - 1).add(p[0] - 1);
}
int[] answer = new int[n];
for (int g = 0; g < n; g++) {
boolean[] used = new boolean[5];
for (int h : adj.get(g)) used[answer[h]] = true;
for (int c = 1; c <= 4; c++) {
if (!used[c]) { answer[g] = c; break; }
}
}
return answer;
}
}vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<vector<int>> adj(n);
for (auto& p : paths) {
adj[p[0] - 1].push_back(p[1] - 1);
adj[p[1] - 1].push_back(p[0] - 1);
}
vector<int> answer(n, 0);
for (int g = 0; g < n; g++) {
bool used[5] = {false};
for (int h : adj[g]) used[answer[h]] = true;
for (int c = 1; c <= 4; c++) {
if (!used[c]) { answer[g] = c; break; }
}
}
return answer;
}Explanation
We must give each garden one of 4 flower types so that no two connected gardens share a type. The wonderful thing here is a simple greedy pass works perfectly, with no backtracking needed.
Why? Every garden has at most 3 paths, so it has at most 3 neighbors. With 4 colors available, at least one color is always free no matter what the neighbors picked. That guarantee is the whole reason greedy never gets stuck.
We build an adjacency list, then visit gardens in order. For the current garden g we collect the set of types already used by its neighbors, then pick the first type from 1, 2, 3, 4 that is not in that set and assign it to answer[g].
Example: n = 4, paths [[1,2],[2,3],[3,4],[4,1],[1,3]]. Garden 1 takes type 1, garden 2 sees 1 is taken so picks 2, garden 3 (neighbor of 1 and 2) picks 3, and garden 4 picks 4, giving [1, 2, 3, 4].
Since each garden only inspects its handful of neighbors and tries at most 4 colors, the whole assignment runs in time proportional to the gardens plus paths.