What is the main algorithmic pattern used in Flower Planting With No Adjacent?

The problem utilizes graph traversal with depth-first search (DFS) to color the graph with a fixed number of colors, ensuring adjacent nodes (gardens) have distinct colors (flower types).

How does DFS help solve the Flower Planting With No Adjacent problem?

DFS allows us to visit each garden and its neighbors, assigning a flower type that hasn’t been used by adjacent gardens. The graph traversal ensures that the constraints are satisfied in an efficient manner.

What are the constraints in the Flower Planting problem?

The problem has a constraint where each garden has at most 3 paths connecting to other gardens, ensuring that there are always enough flower types available to assign to each garden.

Can a breadth-first search (BFS) be used for Flower Planting With No Adjacent?

Yes, BFS can be used as an alternative to DFS for graph traversal. However, DFS is typically simpler to implement for this type of graph coloring problem.

What is the space complexity of the Flower Planting With No Adjacent problem?

The space complexity is O(n + m), where `n` is the number of gardens and `m` is the number of paths, as we store the graph structure and visited nodes during traversal.

#1042

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

不邻接植花

有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [x i , y i ] 描述了花园 x i 到花园 y i 的双向路径。在每个花园中，你打算种下四种花之一。另外，所有花园最多有 3 条路径可以进入或离开. 你需要为每个花园选择一种花，使得通过路径相…

深度优先搜索广度优先搜索图

题目描述

有 n 个花园，按从 1 到 n 标记。另有数组 paths ，其中 paths[i] = [x_i, y_i] 描述了花园 x_i 到花园 y_i 的双向路径。在每个花园中，你打算种下四种花之一。

另外，所有花园最多有 3 条路径可以进入或离开.

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回任一可行的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1、2、3、4 表示。保证存在答案。

示例 1：

输入：n = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]
解释：
花园 1 和 2 花的种类不同。
花园 2 和 3 花的种类不同。
花园 3 和 1 花的种类不同。
因此，[1,2,3] 是一个满足题意的答案。其他满足题意的答案有 [1,2,4]、[1,4,2] 和 [3,2,1]

示例 2：

输入：n = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]

示例 3：

输入：n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]

提示：

1 <= n <= 10⁴
0 <= paths.length <= 2 * 10⁴
paths[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
每个花园最多有 3 条路径可以进入或离开

lightbulb

解题思路

方法一：枚举

我们先根据数组 $\textit{paths}$ 构建图 $g$ ，其中 $g[x]$ 表示与花园 $x$ 相邻的花园列表。

接下来，对于每个花园 $x$ ，我们先找出与 $x$ 相邻的花园 $y$ ，并将 $y$ 花园中种植的花的种类标记为已使用。然后我们从花的种类 $1$ 开始枚举，直到找到一个未被使用的花的种类 $c$ ，将 $c$ 标记为 $x$ 花园中种植的花的种类，然后继续枚举下一个花园。

枚举结束后，返回答案即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是花园的数量和路径的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient use of graph traversal techniques, especially DFS.
question_mark
Check for a proper implementation of the greedy coloring algorithm.
question_mark
Ensure the solution correctly handles edge cases, such as minimal paths or no paths.

warning

常见陷阱

外企场景

error
Incorrectly assuming there might be no valid flower assignments when there are always enough flower types available.
error
Not implementing the graph traversal properly, leading to incorrect flower assignments or missed edges.
error
Overcomplicating the problem with unnecessary data structures when a simple DFS-based greedy approach suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider modifying the number of flower types to test how the algorithm scales with different constraints.
arrow_right_alt
Explore whether a breadth-first search (BFS) approach could provide advantages in some cases over DFS.
arrow_right_alt
Test the algorithm’s performance on large graphs with up to 10^4 gardens and 2 * 10^4 paths.

help

常见问题

外企场景

继续练习

#928 尽量减少恶意软件的传播 II #924 尽量减少恶意软件的传播 #886 可能的二分法