Flower Planting With No Adjacent

Flower Planting With No Adjacent

What is this problem about?

The Flower Planting With No Adjacent interview question is a graph coloring problem. You have n gardens, and some pairs of gardens are connected by paths. You want to plant one of four types of flowers in each garden so that no two connected gardens have the same type of flower. The problem guarantees that any garden is connected to at most 3 other gardens, which mathematically ensures that a valid coloring with 4 colors always exists.

Why is this asked in interviews?

Companies like Bloomberg and Vimeo use this coding problem to evaluate a candidate's understanding of basic graph traversal and the Greedy interview pattern. It’s a "Medium" difficulty task that tests your ability to represent relationships using an adjacency list and to assign states (colors) while avoiding conflicts. It's a simplified version of the general graph coloring problem, made easier by the degree constraint.

Algorithmic pattern used

This problem is solved using a Greedy Graph Coloring approach.

1. Build the Graph: Create an adjacency list to represent which gardens are connected.
2. Iterate: Go through each garden from 1 to n.
3. Check Neighbors: For the current garden, look at all its connected neighbors and note which flower types they already have.
4. Assign: Pick the first flower type (from 1, 2, 3, 4) that is not used by any of the neighbors and assign it to the current garden.

Example explanation

Suppose n = 3 and paths are [[1, 2], [2, 3], [3, 1]] (a triangle).

1. Garden 1: No neighbors have flowers yet. Assign flower 1.
2. Garden 2: Neighbors are 1 (has flower 1) and 3 (empty). Available flowers: 2, 3, 4. Assign flower 2.
3. Garden 3: Neighbors are 1 (flower 1) and 2 (flower 2). Available flowers: 3, 4. Assign flower 3. Result: [1, 2, 3].

Common mistakes candidates make

• Over-complicating: Trying to use Backtracking (DFS) to find a global configuration, which is unnecessary and slow because a valid greedy choice is guaranteed at every step.
• 0-indexing vs 1-indexing: Mixing up the 1-based garden numbers with 0-based array indices.
• Graph representation: Using an adjacency matrix instead of an adjacency list, which wastes memory and increases lookup time for sparse connections.

Interview preparation tip

Whenever a graph problem involves assigning values to nodes with constraints based on neighbors, check the maximum degree (number of edges per node). If the maximum degree is $D$, you can always color the graph greedily with $D+1$ colors.