Flower Planting With No Adjacent

Intuition

Each garden touches at most three others, and we have four flower types available. That gap of one is the whole trick: when we decide a garden's flower, at most three of the four types can possibly be blocked by its neighbors, so at least one type is always free. This means we never need to backtrack. Processing gardens one by one, we simply look at the flowers already chosen for that garden's neighbors and pick the smallest label not among them. Neighbors we have not colored yet contribute no constraint, which is fine because they will adapt around us when their turn comes.

Algorithm walkthrough

1. 1Build an adjacency list so each garden knows its neighbors.
2. 2Create an answer array of length n, initialized to 0 to mean unassigned.
3. 3Iterate over gardens 1 through n in order.
4. 4For the current garden, gather the flower types already assigned to its neighbors into a used set.
5. 5Pick the smallest type in 1..4 that is not in the used set and assign it to the current garden.
6. 6After all gardens are processed, return the answer array.

Implementation

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n + 1)]
        for x, y in paths:
            adj[x].append(y)
            adj[y].append(x)
        answer = [0] * (n + 1)
        for garden in range(1, n + 1):
            used = {answer[nei] for nei in adj[garden]}
            for flower in range(1, 5):
                if flower not in used:
                    answer[garden] = flower
                    break
        return answer[1:]