Domain 2MediumMEDIUM

Flower Planting With No Adjacent

Uses a greedy strategy with an adjacency list to assign flower colors, leveraging the constraint that max degree (3) is less than available colors (4).

Domain: medium•Updated: 2026-09-07
#greedy#adjacency list#$O(n + e)$#$O(N+E)$

Problem Breakdown

We are given n gardens and a set of paths connecting them. Each garden must be assigned one of four flower types such that no two connected gardens share the same type. The graph is undirected, with each node having at most 3 edges (degree ≤3\le 3). This constraint ensures that for any node, there are fewer than 4 neighbors to constrain its color choice.

Intuition

This problem can be modeled as a graph coloring task where we need k=4k=4 colors and the maximum degree of any vertex is Δ≤3\Delta \le 3. Since the number of available colors (kk) exceeds the sum of constraints from neighbors (at most Δ=3\Delta = 3), a greedy approach guarantees success. For every garden, regardless of which neighbor has been processed first or last, there will always be at least one color among {1, 2, 3, 4} that is not currently used by its colored neighbors. We do not need backtracking because the constraints are loose enough (Δ<k\Delta < k).

Approach

  1. Graph Representation: Construct an adjacency list from paths to efficiently access neighbors for any garden ID. Since gardens are labeled 1…n1 \dots n, we map them directly or adjust indices when accessing our result array (0-indexed in Python).
  2. Greedy Coloring Loop: Iterate through each garden from 1 to n. For the current garden, check all its neighbors that have already been assigned a flower type. Collect these used colors into a set.
  3. Color Assignment: Select the smallest integer color (from 1 to 4) not present in the collected neighbor colors and assign it to the current garden. Since unprocessed neighbors contribute no constraints (their value is effectively null/0), this logic holds regardless of processing order, provided we check existing assignments correctly.
  4. Result: Return the populated array where index i corresponds to garden i+1.

Complexity Analysis

  • Time Complexity: O(N+E)O(N + E), where NN is the number of gardens and EE is the number of paths (edges). Building the adjacency list takes linear time with respect to edges. The main loop runs NN times; inside each iteration, we iterate over neighbors. Since max degree ≤3\le 3, neighbor checks are constant per node relative to graph size (O(Δ)O(\Delta)), making total work proportional to sum of degrees which is 2E2E.
  • Space Complexity: O(N+E)O(N + E). We store the adjacency list (proportional to edges and nodes) and a result array of size n.

Solution

from typing import List
import collections

def gardenNoAdj(n: int, paths: List[List[int]]) -> List[int]:
    # Build an undirected graph using a dictionary of lists (adjacency list)
    adj = collections.defaultdict(list)
    
    for u, v in paths:
        adj[u].append(v)
        adj[v].append(u)
        
    # Initialize result array. Index i corresponds to garden i+1. 
    # We use 0 as a placeholder since flower types are 1-4.
    answer = [0] * n
    
    # Iterate through each garden from 1 to n
    for i in range(1, n + 1):
        used_colors = set()
        
        # Check colors of all neighbors that have already been assigned a flower type
        # Note: Even if we process sequentially, checking 'answer' array handles 
        # both processed and unprocessed neighbors correctly because unassigned ones are 0.
        for neighbor in adj[i]:
            if answer[neighbor - 1] != 0:
                used_colors.add(answer[neighbor - 1])
        
        # Assign the smallest available flower type (1-4) that isn't used by neighbors
        for color in range(1, 5):
            if color not in used_colors:
                answer[i - 1] = color
                
    return answer

# Example usage matching LeetCode format logic implicitly handled above.

Edge Cases Handled

  • Single Garden (n=1): The loop runs once for garden 1. No neighbors exist, so it picks flower type 1. Correctly returns [1].
  • No Paths: If paths is empty, the adjacency list remains empty. Every node gets color 1, which satisfies constraints trivially as there are no adjacent conflicts to resolve.
  • Disconnected Graphs: The algorithm processes each component independently because neighbor checks only look at existing edges in adj. A garden with no paths simply picks the first valid color regardless of other components’ choices.