LeetCode 1042: Flower Planting With No Adjacent

Problem Restatement

We have n gardens labeled 1 to n and paths between some gardens.

Each garden must be assigned one of 4 flower types (1 to 4).

No two adjacent gardens (connected by a path) can have the same flower type.

Since each node has at most 3 neighbors (guaranteed by the problem), a valid assignment always exists.

Return a valid assignment as an array answer where answer[i] is the flower type for garden i+1.

The official constraints state that 1 <= n <= 10^4, 0 <= paths.length <= 2 * 10^4, and each node has degree at most 3.

Input and Output

Function shape:

def gardenNoAdj(n: int, paths: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

n = 3, paths = [[1,2],[2,3],[3,1]]

Triangle graph. Assign 1→1, 2→2, 3→3.

Answer:

[1, 2, 3]

Key Insight

Since every node has degree at most 3 and there are 4 colors, at least one color is always available for each node (pigeonhole principle).

Simply assign colors greedily: for each node, pick any color not used by its already-assigned neighbors.

Algorithm

1. Build an adjacency list.
2. For each garden from 1 to n:
   • Find colors used by already-assigned neighbors.
   • Assign the first available color from {1, 2, 3, 4}.

Correctness

Since each node has at most 3 neighbors, the set of used neighbor colors has at most 3 elements. With 4 colors, at least one is always free.

Edge Cases

• Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
• Return the failure value when the destination is unreachable.
• Check grid or graph boundaries before reading neighbors.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import defaultdict

class Solution:
    def gardenNoAdj(self, n: int, paths: list[list[int]]) -> list[int]:
        graph = defaultdict(list)
        for u, v in paths:
            graph[u].append(v)
            graph[v].append(u)

        answer = [0] * (n + 1)

        for garden in range(1, n + 1):
            used = {answer[nb] for nb in graph[garden]}
            for color in range(1, 5):
                if color not in used:
                    answer[garden] = color
                    break

        return answer[1:]

Testing

def run_tests():
    s = Solution()

    result = s.gardenNoAdj(3, [[1,2],[2,3],[3,1]])
    for u, v in [[1,2],[2,3],[3,1]]:
        assert result[u-1] != result[v-1]

    result = s.gardenNoAdj(4, [[1,2],[3,4]])
    for u, v in [[1,2],[3,4]]:
        assert result[u-1] != result[v-1]

    print("all tests passed")

run_tests()