MediumDepth-First SearchBreadth-First SearchGraphGreedy

Flower Planting With No Adjacent

1 approach, code in every language

You have n gardens labeled from 1 to n, and a list of bidirectional paths where each path [x, y] connects garden x and garden y. Every garden is directly connected to at most three other gardens.

There are four kinds of flowers, labeled 1, 2, 3, and 4. You must plant exactly one kind of flower in each garden so that any two gardens joined by a path use different kinds of flowers.

Return any valid assignment as an array of length n, where the i-th value is the flower type planted in garden i + 1. The problem guarantees that at least one valid answer exists.

Example 1

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

Output: [1,2,3]

The three gardens form a triangle, so each must differ from the other two. Assigning 1, 2, and 3 satisfies every path; any permutation of three distinct types also works.

Example 2

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

Output: [1,2,1,2]

Gardens 1 and 2 must differ and gardens 3 and 4 must differ, but the two pairs are independent, so the pattern 1, 2, 1, 2 is valid.

Constraints

1 <= n <= 10^4
0 <= paths.length <= 2 * 10^4
paths[i].length == 2
1 <= x, y <= n
x != y
Every garden has at most 3 paths connected to it

Greedy Coloring

Visit gardens in order and give each the smallest flower type in 1..4 not already used by an assigned neighbor; a free type always exists because degree is at most 3.

Loading animation…

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

1Build an adjacency list so each garden knows its neighbors.
2Create an answer array of length n, initialized to 0 to mean unassigned.
3Iterate over gardens 1 through n in order.
4For the current garden, gather the flower types already assigned to its neighbors into a used set.
5Pick the smallest type in 1..4 that is not in the used set and assign it to the current garden.
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:]

Time

O(n + e)

Space

O(n + e)

e is the number of paths. Each garden checks at most three neighbors and four flower types, so per-garden work is constant. The adjacency list uses O(n + e) space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free