1042. Flower Planting With No Adjacent

Reformulated question¶

Assign each of n gardens one flower type in {1,2,3,4} so that connected gardens have different types.

Because each garden has degree at most 3, a valid assignment always exists.

Compact example:

Input:  n=3, paths=[[1,2],[2,3],[3,1]]
Output: [1,2,3]

Meaning:
- garden 1 touches 2 and 3
- garden 2 touches 1 and 3
- garden 3 touches 1 and 2
- adjacent gardens must differ

Key Trick¶

Use greedy graph coloring.

For each garden, look at colors already used by its neighbors, then pick any color from {1,2,3,4} not used there.

Why it works:

each garden has at most 3 neighbors
so at most 3 colors can be blocked
with 4 colors, one color is always available

Trap¶

Common mistakes:

forgetting gardens are 1-indexed in paths but Python lists are 0-indexed
overcomplicating it with backtracking or DFS coloring
checking all neighbors, including uncolored ones, as if they already forbid color 0
assuming the graph is connected
building extra state for "allowed colors" when local neighbor check is enough

Why Is This Question Interesting?¶

It looks like general graph coloring, which is hard, but the degree bound <= 3 makes a simple greedy solution correct.

So the interview trick is to notice the strong constraint and avoid unnecessary search.

Solution with Idiomatic Python¶

from typing import List


class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        # Build adjacency list for gardens 1..n.
        graph = [[] for _ in range(n)]
        for x, y in paths:
            graph[x - 1].append(y - 1)
            graph[y - 1].append(x - 1)

        # 0 means "uncolored".
        ans = [0] * n

        for garden in range(n):
            # Colors already used by colored neighbors.
            used = set()
            for nei in graph[garden]:
                if ans[nei] != 0:
                    used.add(ans[nei])

            # Pick the first available color.
            for color in range(1, 5):
                if color not in used:
                    ans[garden] = color
                    break

        return ans

Pytest Test¶

import pytest

from typing import List


def is_valid_coloring(n: int, paths: List[List[int]], ans: List[int]) -> bool:
    if len(ans) != n:
        return False
    if any(color not in {1, 2, 3, 4} for color in ans):
        return False
    return all(ans[a - 1] != ans[b - 1] for a, b in paths)


@pytest.mark.parametrize(
    ("n", "paths"),
    [
        (1, []),
        (3, [[1, 2], [2, 3], [3, 1]]),
        (4, [[1, 2], [3, 4]]),
        (4, [[1, 2], [2, 3], [3, 4], [4, 1]]),
        (5, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 1]]),
        (4, [[1, 2], [1, 3], [1, 4]]),
        (6, [[1, 2], [2, 3], [4, 5]]),
    ],
)
def test_garden_no_adj(n, paths):
    ans = Solution().gardenNoAdj(n, paths)
    assert is_valid_coloring(n, paths, ans)

Comment on Your Solution¶

Good idea:

you correctly model the graph and greedily assign colors

Main issues:

if gg: is a bug-prone check
- gg is a garden index, always nonzero here
- you meant to check gg_flower
flower_allowed is unnecessary
- only current neighbors' chosen colors matter
flower_allowed[g].remove(f) has no effect later
- that set is never used to constrain neighbors
extra sets/dicts make the code longer than needed for a simple greedy solution
top-level a = set() and import pytest are unrelated to the solution
missing List import would fail as written

A simpler interview-ready version is better:

build adjacency list
for each garden, collect neighbor colors already assigned
choose any color in 1..4 not used

# Pass leetcode tests (but code not correct)
class Solution:
    def gardenNoAdj(self, n: int, paths: list[list[int]]) -> list[int]:
        paths_dict = {g:set() for g in range(1, n+1)}
        for g1,g2 in paths:
            paths_dict[g1].add(g2)
            paths_dict[g2].add(g1)
        answer = [0] * n
        flower_allowed = {g:{1,2,3,4} for g in range(1, n+1)}
        for g in paths_dict:
            g_allowed = flower_allowed[g]
            g_not_allowed = set()
            for gg in paths_dict[g]:
                gg_flower = answer[gg - 1]
                if gg:
                    g_not_allowed.add(gg_flower)
            g_allowed = g_allowed.difference(g_not_allowed)
            f = g_allowed.pop()
            answer[g - 1] = f
            flower_allowed[g].remove(f)
        return answer

# Written after reading AI comments
# WRONG
class Solution:
    def gardenNoAdj(self, n: int, paths: list[list[int]]) -> list[int]:
        neighbors = {g:set() for g in range(1, n+1)}
        for g1,g2 in paths:
            neighbors[g1].add(g2)
            neighbors[g2].add(g1)
        answer = [0] * n
        for i in range(n):
            neighbor_flowers = {answer[g - 1] for g in neighbors[i + 1] if answer[g - 1] != 0}
            flowers = {1,2,3,4}.difference(neighbor_flowers)
            answer[i - 1] = flowers.pop()
        return answer

Extra¶

While I completely understood the solution, it was the first time I work with graph that way and was missing context and vocabulary. So I asked AI for help.

When you see this problem, the missing pattern is:

items = nodes
pairwise constraints = edges
assign one label/value per node so adjacent nodes differ = graph coloring

1. Graph¶

A graph is just:

vertices/nodes
- the things
edges
- the relationships between things

In this problem:

gardens = nodes
paths between gardens = edges

So this input:

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

means this graph:

1 -- 2 -- 3
|
4

Why graphs matter:

many interview problems are really "objects + connections"
as soon as you read:
- "connected to"
- "depends on"
- "neighbor"
- "friend"
- "road/path/flight"
- "adjacent"
you should think: maybe this is a graph

2. Graph coloring¶

Graph coloring means:

give a color/value/type to each node
with a rule like:
- adjacent nodes must have different colors

In your problem:

flower type = color
path = adjacency constraint
so "flower planting" is just graph coloring with 4 colors

Tiny example:

1 -- 2
 \  /
  3

A valid coloring is:

1 -> red
2 -> blue
3 -> green

Recognition pattern:

"assign categories to connected items"
"neighbors must be different"
"minimum/limited number of labels/colors"

That is usually a coloring-style problem.

Important note:

general graph coloring can be hard
but this problem gives a special gift:
- each node has degree at most 3
- you have 4 colors
that makes greedy enough

3. Greedy algorithms¶

A greedy algorithm means:

make a good local choice now
do not backtrack
hope or prove this leads to a valid/global solution

In this problem, greedy is:

process gardens one by one
for current garden, look at already-colored neighbors
pick any color not used by them

Why greedy works here:

a garden has at most 3 neighbors
so at most 3 colors are blocked
there are 4 colors
therefore one color is always available

That is the key proof.

The fast recognition shortcut¶

When reading a problem, ask:

what are the entities?
- maybe nodes
what are the pair relations?
- maybe edges
do I need to assign a choice/value/type to each entity?
do connected entities have constraints?
- same/different, before/after, allowed/not allowed

If yes, it is often a graph problem.

More specifically:

"connected items must differ"
- graph coloring
"visit/reach/count components"
- DFS/BFS
"dependency order"
- topological sort
"shortest route/cost"
- shortest path

For this exact problem, the vocabulary to remember¶

graph
node / vertex
edge
adjacency list
degree of a node
- number of neighbors
graph coloring
greedy coloring
constraint satisfaction

Best mental translation for this problem:

"gardens with paths" -> graph
"flower types" -> colors
"adjacent gardens differ" -> coloring constraint
"each garden has at most 3 neighbors, 4 colors available" -> greedy always works

One-sentence memory hook¶

If a problem says "assign one of a few types to connected items so neighbors differ", think:

graph coloring
and if the constraints are small enough, try greedy first