Flower Planting With No Adjacent: Greedy Graph Coloring

You have n gardens labeled 1 through n, and a list of bidirectional paths connecting them. Each garden has at most 3 paths. Your job is to plant one of 4 flower types in each garden so that no two connected gardens have the same flower type. Return an array where answer[i] is the flower type for garden i + 1.

This is LeetCode 1042: Flower Planting With No Adjacent, and it is a clean example of greedy graph coloring. The constraint that every node has at most 3 neighbors, combined with 4 available colors, makes it so a simple greedy pass always finds a valid assignment.

Why this problem matters

Graph coloring is a classic problem in computer science. In general, deciding whether a graph can be colored with k colors is NP-complete. But this problem hands you a special case: the maximum degree of any node is 3, and you have 4 colors. That means you never run out of options.

This is a direct application of a well-known theorem: any graph can be greedily colored with at most d + 1 colors, where d is the maximum degree. Since d is 3 here, 4 colors are always enough. No backtracking, no clever heuristics, just iterate through the nodes and pick the first available color.

Understanding this pattern helps you recognize when a problem that looks complex actually has a simple greedy solution. The constraint in the problem statement (at most 3 paths per garden) is the clue.

The key insight

Each garden has at most 3 neighbors. With 4 flower types, at least one type is always unused by the neighbors. So you can process gardens in any order, and for each one, just pick the smallest flower type that none of its already-colored neighbors are using.

There is no need for backtracking or BFS/DFS traversal. A single linear scan through all gardens works. The constraint guarantees that the greedy choice is always valid.

The solution

def gardenNoAdj(n, paths):
    graph = [[] for _ in range(n)]
    for u, v in paths:
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    result = [0] * n
    for i in range(n):
        used = {result[j] for j in graph[i]}
        for color in range(1, 5):
            if color not in used:
                result[i] = color
                break
    return result

First, build an adjacency list from the edge list. The gardens are 1-indexed in the input, so we convert to 0-indexed for the array.

Then iterate through each garden. For the current garden, collect all the flower types already assigned to its neighbors into a set called used. Then try flower types 1 through 4 in order. The first one not in used is the answer for this garden.

Because each garden has at most 3 neighbors, the used set has at most 3 elements (plus possibly 0 for uncolored neighbors, which we skip naturally). Out of 4 flower types, at least one is always available.

Visual walkthrough

Let's trace the greedy algorithm on a 4-garden graph where garden 1 connects to gardens 2, 3, and 4 (the maximum 3 neighbors). Watch how each step always has an available flower.

Notice that garden 4 gets flower 2 even though garden 2 also has flower 2. That is fine because gardens 2 and 4 are not directly connected. The constraint only applies to adjacent gardens.

Complexity analysis

where n = number of gardens and p = number of paths.

Time: Building the adjacency list takes O(n + p). The greedy loop visits each garden once and checks at most 3 neighbors per garden, which is O(1) per garden. Total: O(n + p).

Space: The adjacency list stores 2 entries per edge (one in each direction), so it uses O(n + p). The result array uses O(n). Total: O(n + p).

The building blocks

1. Adjacency list construction

Converting an edge list into an adjacency list is one of the most common graph setup patterns:

graph = [[] for _ in range(n)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

For undirected graphs, you add each edge in both directions. For directed graphs, you only add one direction. This pattern appears in virtually every graph problem, from Course Schedule to Clone Graph.

2. Greedy coloring with set difference

The core coloring logic collects the "used" colors from neighbors and picks the first available one:

used = {result[j] for j in graph[i]}
for color in range(1, num_colors + 1):
    if color not in used:
        result[i] = color
        break

This is a reusable pattern any time you need to assign a label from a small set while avoiding conflicts with neighbors. The set comprehension makes the lookup O(1), and iterating through colors in order gives you the smallest available option.

Edge cases

• No paths at all: every garden is isolated. Each gets flower 1. The greedy loop assigns color 1 to every node since used is always empty (just containing 0).
• Single garden: n = 1, no paths. Return [1].
• Disconnected components: the greedy approach works regardless of connectivity. Each garden is colored based only on its actual neighbors, so disconnected components are handled automatically.
• Garden with exactly 3 neighbors, all different colors: the fourth color is always available. This is the worst case, and greedy still works.
• Linear chain of gardens: each garden has at most 2 neighbors, so you only need 3 colors. The greedy algorithm alternates between colors naturally.

From understanding to recall

The greedy coloring solution is short, but the reasoning behind it matters. You need to recognize the degree constraint, know why d + 1 colors suffice for greedy coloring, and translate that into the set-difference pattern. During an interview, spotting that "at most 3 neighbors + 4 colors = greedy works" is the entire battle.

Spaced repetition helps you build that recognition automatically. You practice the adjacency list setup, the greedy color assignment loop, and the degree-based reasoning until they become reflexes. When a graph coloring problem appears, you do not need to re-derive the theory. You just write the code.

Related posts

• Course Schedule - Graph traversal with adjacency lists
• Clone Graph - Graph representation and traversal
• Is Graph Bipartite? - Graph coloring with two colors

CodeBricks breaks Flower Planting With No Adjacent into its adjacency-list-construction and greedy-coloring building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained coloring problem shows up in your interview, you recognize the degree argument and write the solution without hesitation.