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 != yiThe problem can be modeled as a graph coloring task. Each garden represents a node, and each path represents an undirected edge. The goal is to assign one of four flower types to every garden such that no two connected gardens share the same type.
A key observation is that every garden has at most three paths. Since there are 4 flower types available, there will always be at least one valid flower choice that differs from all adjacent gardens. This makes a greedy coloring approach feasible.
First, build an adjacency list to represent the graph. Then iterate through each garden and check the flower types already assigned to its neighbors. From the set of four possible flowers, choose one that is not used by any adjacent node.
This strategy avoids complex backtracking and works efficiently because of the degree constraint. The algorithm effectively performs a lightweight graph traversal similar to DFS/BFS reasoning while assigning colors greedily.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Graph Coloring with Adjacency List | O(N + P) | O(N + P) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Since each garden is connected to at most 3 gardens, there's always an available color for each garden. For example, if one garden is next to gardens with colors 1, 3, 4, then color #2 is available.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Each garden can have at most three adjacent gardens. With four available flower types, there will always be at least one type that is different from all neighboring gardens, ensuring a valid assignment.
Yes, this problem is a common interview-style question because it tests graph modeling and greedy reasoning. Variants of graph coloring and constraint assignment frequently appear in technical interviews at top tech companies.
An adjacency list is the most suitable data structure because it efficiently represents connections between gardens. It allows quick lookup of neighboring gardens when deciding which flower type can be assigned safely.
The optimal approach treats the problem as a graph coloring task. By building an adjacency list and greedily assigning one of four flower types not used by neighboring gardens, you can guarantee a valid solution due to the maximum degree constraint of three.