# 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

| Item | Meaning |
|---|---|
| Input | `n` gardens and `paths` list |
| Output | Array of flower types `1-4` for each garden |

Function shape:

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

## Examples

Example 1:

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

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

Answer:

```python
[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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n + p)` | Build graph and process each node |
| Space | `O(n + p)` | Adjacency list |

## 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

```python
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

```python
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()
```

| Test | Verification | Why |
|---|---|---|
| Triangle | No adjacent gardens share a color | Degree-3 graph, 4 colors |
| Two disjoint edges | No adjacent gardens share a color | Simple case |