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 ). 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 colors and the maximum degree of any vertex is . Since the number of available colors () exceeds the sum of constraints from neighbors (at most ), 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 ().
Approach
- Graph Representation: Construct an adjacency list from
pathsto efficiently access neighbors for any garden ID. Since gardens are labeled , we map them directly or adjust indices when accessing our result array (0-indexed in Python). - 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. - 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.
- Result: Return the populated array where index
icorresponds to gardeni+1.
Complexity Analysis
- Time Complexity: , where is the number of gardens and is the number of paths (edges). Building the adjacency list takes linear time with respect to edges. The main loop runs times; inside each iteration, we iterate over neighbors. Since max degree , neighbor checks are constant per node relative to graph size (), making total work proportional to sum of degrees which is .
- Space Complexity: . 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 garden1. No neighbors exist, so it picks flower type1. Correctly returns[1]. - No Paths: If
pathsis empty, the adjacency list remains empty. Every node gets color1, 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.