LeetCode 1042: Flower Planting With No Adjacent (Graph Coloring with 4 Choices)
LeetCode 1042Graph ColoringGreedyToday we solve LeetCode 1042 - Flower Planting With No Adjacent.
Source: https://leetcode.com/problems/flower-planting-with-no-adjacent/
English
Problem Summary
There are n gardens and bidirectional paths between some pairs. We need to assign one flower type from 1..4 to each garden so that adjacent gardens always have different types.
Key Insight
Each garden has at most 3 neighbors, but we have 4 flower types. So when we process a garden, at least one type is always available if we avoid colors used by its already-colored neighbors.
Algorithm
- Build an adjacency list.
- Visit gardens from 1 to n.
- Mark flower types used by colored neighbors.
- Pick the first free type in 1..4.
Complexity Analysis
Time: O(n + m), where m is number of paths.
Space: O(n + m).
Common Pitfalls
- Forgetting paths are undirected.
- Using 0-index/1-index inconsistently.
- Assuming backtracking is required. For this constraint, greedy assignment is sufficient.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int[] gardenNoAdj(int n, int[][] paths) {
List<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] p : paths) {
int u = p[0] - 1, v = p[1] - 1;
g[u].add(v);
g[v].add(u);
}
int[] color = new int[n];
for (int i = 0; i < n; i++) {
boolean[] used = new boolean[5];
for (int nb : g[i]) used[color[nb]] = true;
for (int c = 1; c <= 4; c++) {
if (!used[c]) {
color[i] = c;
break;
}
}
}
return color;
}
}func gardenNoAdj(n int, paths [][]int) []int {
g := make([][]int, n)
for _, p := range paths {
u, v := p[0]-1, p[1]-1
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
color := make([]int, n)
for i := 0; i < n; i++ {
used := [5]bool{}
for _, nb := range g[i] {
used[color[nb]] = true
}
for c := 1; c <= 4; c++ {
if !used[c] {
color[i] = c
break
}
}
}
return color
}class Solution {
public:
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<vector<int>> g(n);
for (auto &p : paths) {
int u = p[0] - 1, v = p[1] - 1;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> color(n, 0);
for (int i = 0; i < n; ++i) {
bool used[5] = {false, false, false, false, false};
for (int nb : g[i]) used[color[nb]] = true;
for (int c = 1; c <= 4; ++c) {
if (!used[c]) {
color[i] = c;
break;
}
}
}
return color;
}
};from typing import List
class Solution:
def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
g = [[] for _ in range(n)]
for u, v in paths:
u -= 1
v -= 1
g[u].append(v)
g[v].append(u)
color = [0] * n
for i in range(n):
used = [False] * 5
for nb in g[i]:
used[color[nb]] = True
for c in range(1, 5):
if not used[c]:
color[i] = c
break
return color/**
* @param {number} n
* @param {number[][]} paths
* @return {number[]}
*/
var gardenNoAdj = function(n, paths) {
const g = Array.from({ length: n }, () => []);
for (const [a, b] of paths) {
const u = a - 1, v = b - 1;
g[u].push(v);
g[v].push(u);
}
const color = Array(n).fill(0);
for (let i = 0; i < n; i++) {
const used = Array(5).fill(false);
for (const nb of g[i]) used[color[nb]] = true;
for (let c = 1; c <= 4; c++) {
if (!used[c]) {
color[i] = c;
break;
}
}
}
return color;
};中文
题目概述
有 n 个花园，以及若干双向路径。需要给每个花园分配 1..4 中一种花，使任意相邻花园的花种不同。
核心思路
每个花园最多只有 3 个邻居，而可选花种有 4 种。按顺序处理花园时，只要避开已着色邻居使用的花种，就一定还能选到一种可用颜色。
算法步骤
- 先构建邻接表。
- 从 1 到 n 顺序处理每个花园。
- 统计已着色邻居占用的花种。
- 在 1..4 中选择第一个未被占用的花种。
复杂度分析
时间复杂度：O(n + m)（m 为路径数）。
空间复杂度：O(n + m)。
常见陷阱
- 忘记路径是无向边，导致只连一侧。
- 下标从 1 转 0 时处理错误。
- 误以为必须回溯。该题在约束下贪心即可。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int[] gardenNoAdj(int n, int[][] paths) {
List<Integer>[] g = new ArrayList[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] p : paths) {
int u = p[0] - 1, v = p[1] - 1;
g[u].add(v);
g[v].add(u);
}
int[] color = new int[n];
for (int i = 0; i < n; i++) {
boolean[] used = new boolean[5];
for (int nb : g[i]) used[color[nb]] = true;
for (int c = 1; c <= 4; c++) {
if (!used[c]) {
color[i] = c;
break;
}
}
}
return color;
}
}func gardenNoAdj(n int, paths [][]int) []int {
g := make([][]int, n)
for _, p := range paths {
u, v := p[0]-1, p[1]-1
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
color := make([]int, n)
for i := 0; i < n; i++ {
used := [5]bool{}
for _, nb := range g[i] {
used[color[nb]] = true
}
for c := 1; c <= 4; c++ {
if !used[c] {
color[i] = c
break
}
}
}
return color
}class Solution {
public:
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<vector<int>> g(n);
for (auto &p : paths) {
int u = p[0] - 1, v = p[1] - 1;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> color(n, 0);
for (int i = 0; i < n; ++i) {
bool used[5] = {false, false, false, false, false};
for (int nb : g[i]) used[color[nb]] = true;
for (int c = 1; c <= 4; ++c) {
if (!used[c]) {
color[i] = c;
break;
}
}
}
return color;
}
};from typing import List
class Solution:
def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
g = [[] for _ in range(n)]
for u, v in paths:
u -= 1
v -= 1
g[u].append(v)
g[v].append(u)
color = [0] * n
for i in range(n):
used = [False] * 5
for nb in g[i]:
used[color[nb]] = True
for c in range(1, 5):
if not used[c]:
color[i] = c
break
return color/**
* @param {number} n
* @param {number[][]} paths
* @return {number[]}
*/
var gardenNoAdj = function(n, paths) {
const g = Array.from({ length: n }, () => []);
for (const [a, b] of paths) {
const u = a - 1, v = b - 1;
g[u].push(v);
g[v].push(u);
}
const color = Array(n).fill(0);
for (let i = 0; i < n; i++) {
const used = Array(5).fill(false);
for (const nb of g[i]) used[color[nb]] = true;
for (let c = 1; c <= 4; c++) {
if (!used[c]) {
color[i] = c;
break;
}
}
}
return color;
};
Comments