Watch 10 video solutions for Flower Planting With No Adjacent, a medium level problem involving Depth-First Search, Breadth-First Search, Graph. This walkthrough by Fraz has 9,245 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.
All gardens have at most 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] Explanation: Gardens 1 and 2 have different types. Gardens 2 and 3 have different types. Gardens 3 and 1 have different types. Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].
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]
Constraints:
1 <= n <= 1040 <= paths.length <= 2 * 104paths[i].length == 21 <= xi, yi <= nxi != yiProblem Overview: You have n gardens connected by bidirectional paths. Each garden must be assigned one of four flower types so that no connected gardens share the same type. The task is to return a valid assignment for all gardens.
Approach 1: Greedy Coloring Approach (O(n + p) time, O(n + p) space)
This problem reduces to a small-scale graph coloring task. Each garden is a node and each path represents an edge. Because the constraint guarantees that every garden has at most 3 neighbors, four flower types are always enough to color the graph. Build an adjacency list and iterate through each garden. For the current garden, check the flower types already assigned to its neighbors, mark them as unavailable, and choose any remaining type from 1..4. This greedy assignment works because at most three colors can be blocked at any step.
The key insight is that the degree of each node is ≤ 3, so at least one of the four colors will always remain valid. No backtracking is required. Each edge is processed when building the adjacency list and each node checks at most three neighbors, giving O(n + p) time where p is the number of paths. This approach directly models the problem as a graph coloring task and is the simplest and fastest implementation.
Approach 2: Depth-First Search (DFS) Coloring (O(n + p) time, O(n + p) space)
A traversal-based approach uses Depth-First Search to color the graph while exploring connected components. Construct an adjacency list, then start DFS from any uncolored garden. When visiting a node, inspect the colors of its neighbors and pick the first valid flower type not already used. Continue recursively for all adjacent gardens until the component is fully colored.
This method is useful when you want a general graph traversal framework that works even if the graph has multiple disconnected components. The DFS ensures every node is visited once and every edge is considered during traversal. The complexity remains O(n + p) time with O(n + p) space due to the adjacency list and recursion stack. A similar traversal could also be implemented using Breadth-First Search.
Recommended for interviews: The Greedy Coloring approach is what most interviewers expect. It shows you recognized the degree constraint and simplified the problem into a deterministic graph coloring step without recursion. Implementing DFS still demonstrates strong understanding of graph traversal, but the greedy solution highlights the key observation that four colors always guarantee a valid assignment.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Coloring | O(n + p) | O(n + p) | Best choice when node degree is small and a fixed number of colors guarantees a solution |
| Depth-First Search (DFS) Coloring | O(n + p) | O(n + p) | Useful when applying a standard graph traversal or handling multiple disconnected components |