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.
This approach involves using a greedy algorithm to assign a flower type to each garden. Since each garden can have at most 3 neighbors, we have a maximum degree of 3, making it feasible to find a suitable flower type from 4 options.
We traverse each garden and assign a flower type that is different from its connected gardens. Since a maximum of 3 colors (flowers) are unavailable from any adjacent gardens, there will always be at least one flower type left to choose from.
In the C implementation, we initialize a graph adjacency list with a fixed size of 3 for each garden. For each garden, we keep a track of used flower types and assign the first available flower type that is not used by its neighbors. This ensures the problem constraints are satisfied.
Time Complexity: O(N + E), where N is the number of gardens and E is the number of paths. Due to constant operation per node, operations primarily include checking colors and assigning them.
Space Complexity: O(N), which is used for storing flower types and the adjacency list of the graph.
This approach utilizes DFS to traverse through each garden from 1 to N. During the DFS traversal, each garden is visited, and an available flower type is assigned that’s different from its neighbor gardens. The recursion carries the assigned value to every adjacent garden, ensuring no conflicts occur.
Though DFS might not be as efficient as a greedy approach generally, it's effective here because of the specific constraints that at most 3 paths per garden exist, and because of the graph's structure.
For the C code, we implement a DFS function to navigate through the graph. Using a matrix to depict the graph, each node calls the DFS function to check its adjacency lists and assigns an available type. This traversal ensures no neighboring nodes have the same flower type.
Time Complexity: O(N + E), since we're exploring each garden and its connections once in DFS.
Space Complexity: O(N), which is the memory used by the flowers array and the recursion stack in the DFS call.
We first construct a graph g based on the array paths, where g[x] represents the list of gardens adjacent to garden x.
Next, for each garden x, we first find the gardens y adjacent to x and mark the types of flowers planted in garden y as used. Then, we enumerate the flower types starting from 1 until we find a flower type c that has not been used. We assign c as the flower type for garden x and continue to the next garden.
After the enumeration is complete, we return the result.
The time complexity is O(n + m), and the space complexity is O(n + m), where n is the number of gardens and m is the number of paths.
| Approach | Complexity |
|---|---|
| Greedy Coloring Approach | Time Complexity: O(N + E), where N is the number of gardens and E is the number of paths. Due to constant operation per node, operations primarily include checking colors and assigning them. Space Complexity: O(N), which is used for storing flower types and the adjacency list of the graph. |
| Depth-First Search (DFS) Approach | Time Complexity: O(N + E), since we're exploring each garden and its connections once in DFS. Space Complexity: O(N), which is the memory used by the flowers array and the recursion stack in the DFS call. |
| Enumeration | — |
| 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 |
Leetcode 1042. Flower Planting With No Adjacent • Fraz • 9,245 views views
Watch 9 more video solutions →Practice Flower Planting With No Adjacent with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor