{x}
blog image

Flower Planting With No Adjacent

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 <= 104
  • 0 <= paths.length <= 2 * 104
  • paths[i].length == 2
  • 1 <= xi, yi <= n
  • xi != yi
  • Every garden has at most 3 paths coming into or leaving it.

Solution Explanation:

This problem can be efficiently solved using a greedy approach combined with graph representation. The core idea is to iterate through each garden and assign it the first available flower color that doesn't conflict with its neighbors. Since each garden has at most three neighbors, there will always be at least one available color.

1. Graph Representation:

The input paths represents edges in an undirected graph where each garden is a node. We can represent this graph using an adjacency list for efficient neighbor lookup. Each index in the adjacency list corresponds to a garden, and the value at that index is a list of its neighboring gardens.

2. Greedy Color Assignment:

We iterate through the gardens (nodes). For each garden:

  • We create a used set (or boolean array) to track flower colors already used by its neighbors.
  • We iterate through the flower colors (1 to 4).
  • If a color is not in the used set, we assign that color to the current garden and move to the next garden. The guarantee that a solution exists ensures this process will always find an available color.

3. Time and Space Complexity Analysis:

  • Time Complexity: O(V + E), where V is the number of gardens (nodes) and E is the number of paths (edges). Building the adjacency list takes O(E) time. Iterating through the gardens and their neighbors takes O(V + E) time in the worst case.
  • Space Complexity: O(V + E). The adjacency list takes O(V + E) space in the worst case. The used set/array for each garden has a constant size (at most 4 colors).

Code Explanation (Python):

from collections import defaultdict
 
class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        g = defaultdict(list)  # Adjacency list to represent the graph
        for x, y in paths:
            x, y = x - 1, y - 1 # Adjust to 0-based indexing
            g[x].append(y)
            g[y].append(x)
        ans = [0] * n # Initialize flower assignments for each garden
        for x in range(n):
            used = {ans[y] for y in g[x]} #Set of used colors by neighbors
            for c in range(1, 5): #Try colors 1 to 4
                if c not in used:
                    ans[x] = c
                    break
        return ans

The other language implementations follow a similar structure, adapting the data structures and syntax accordingly. The core algorithm remains the same greedy color assignment using an adjacency list representation of the graph.