Problem Description
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. 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 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.
Key Insights
- Each garden can be viewed as a node in a graph, and each path as an edge.
- The problem can be interpreted as a graph coloring problem, where we need to color the nodes (gardens) such that no two adjacent nodes (connected gardens) share the same color (flower type).
- Since every garden has at most 3 paths, we only need to choose from 4 colors (flower types).
- A greedy approach can be employed to assign flower types while ensuring no two adjacent gardens have the same type.
Space and Time Complexity
Time Complexity: O(n + m), where n is the number of gardens and m is the number of paths. Space Complexity: O(n + m) for storing the graph representation.
Solution
The solution utilizes a graph representation where gardens are nodes and paths are edges. We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and assign flower types. During the traversal, we maintain a set of available flower types and assign a flower type to each garden that is not used by its adjacent gardens. This ensures that no two connected gardens have the same flower type.