LeetCode 1042 - Flower Planting With No Adjacent

The problem presents n gardens, labeled from 1 to n, and a list of bidirectional paths connecting pairs of gardens. Each garden must be planted with one of four types of flowers (1 through 4).

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theory

LeetCode Problem 1042

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem presents n gardens, labeled from 1 to n, and a list of bidirectional paths connecting pairs of gardens. Each garden must be planted with one of four types of flowers (1 through 4). The constraint is that no two gardens connected by a path can have the same type of flower. The task is to return any valid assignment of flower types for all gardens.

The input consists of an integer n representing the number of gardens and an array paths representing garden connections. Each element in paths is a pair [xi, yi] indicating a two-way path. The output should be an array answer of length n, where answer[i] represents the flower type planted in garden i+1.

Constraints provide important guarantees: each garden has at most 3 paths. This implies that with 4 flower types available, it is always possible to choose a flower type not used by neighboring gardens, guaranteeing a solution exists. The input size can be as large as n = 10^4 and up to 2 * 10^4 paths, meaning a naive brute-force enumeration of all flower assignments would be too slow.

Important edge cases include:

  • A garden with no paths, which can safely take any flower.
  • A garden connected to the maximum of 3 neighbors, where careful selection is required.
  • Fully connected subsets (triangles) of gardens, which are still solvable due to the four flower types.

Approaches

Brute Force

A naive brute-force approach would attempt to assign flowers recursively to each garden, backtracking whenever a neighbor has the same flower. While correct, this method is exponential in time complexity (O(4^n)), because every garden has 4 choices and the search space grows combinatorially. This is impractical for n up to 10^4.

Optimal Approach

The key observation is that each garden has at most 3 neighbors and there are 4 flower types, which guarantees at least one available flower for every garden. We can adopt a greedy approach:

  1. Represent the gardens and paths as an adjacency list.
  2. Iterate through each garden in order.
  3. Check the flower types assigned to its neighbors.
  4. Assign the smallest-numbered flower not used by neighbors.

This approach ensures a valid assignment in a single pass and leverages the problem constraint that a solution always exists.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^n) O(n) Tries every combination recursively; impractical
Greedy Assignment (Optimal) O(n + e) O(n + e) Uses adjacency list and assigns flowers in a single pass

Algorithm Walkthrough

  1. Initialize an adjacency list graph mapping each garden to a list of its neighboring gardens.
  2. For each path [u, v] in paths, add v to graph[u] and u to graph[v].
  3. Initialize an array answer of length n with zeros, representing unassigned flowers.
  4. Iterate over each garden from 1 to n.
  5. For the current garden, create a set of flower types already used by its neighbors.
  6. Assign the smallest flower type from 1 to 4 that is not in the set of neighbors' flowers.
  7. Continue until all gardens have an assigned flower.
  8. Return answer.

Why it works: Since each garden has at most 3 neighbors and there are 4 flower types, there is always at least one flower type not used by neighbors. By greedily assigning the smallest available flower to each garden, the algorithm ensures all constraints are satisfied.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for u, v in paths:
            graph[u].append(v)
            graph[v].append(u)
        
        answer = [0] * n
        
        for garden in range(1, n + 1):
            used = {answer[neighbor - 1] for neighbor in graph[garden] if answer[neighbor - 1] != 0}
            for flower in range(1, 5):
                if flower not in used:
                    answer[garden - 1] = flower
                    break
        
        return answer

Explanation: We first build a graph using a defaultdict to store neighbors. Then, for each garden, we track flower types already used by neighbors in a set. Iterating over flower types from 1 to 4, we assign the first available flower to the garden. This ensures no two adjacent gardens share a flower.

Go Solution

func gardenNoAdj(n int, paths [][]int) []int {
    graph := make([][]int, n+1)
    for _, path := range paths {
        u, v := path[0], path[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
    
    answer := make([]int, n)
    
    for garden := 1; garden <= n; garden++ {
        used := make(map[int]bool)
        for _, neighbor := range graph[garden] {
            if answer[neighbor-1] != 0 {
                used[answer[neighbor-1]] = true
            }
        }
        for flower := 1; flower <= 4; flower++ {
            if !used[flower] {
                answer[garden-1] = flower
                break
            }
        }
    }
    
    return answer
}

Go-specific notes: We use slices for adjacency lists and a map to track used flower types. Arrays are 0-indexed, while garden labels are 1-indexed, so we adjust indices appropriately. The logic mirrors the Python version closely.

Worked Examples

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

Garden Neighbors Used Flowers Assigned Flower
1 2, 3 {} 1
2 1, 3 {1} 2
3 1, 2 {1, 2} 3

Output: [1, 2, 3]

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

Garden Neighbors Used Flowers Assigned Flower
1 2 {} 1
2 1 {1} 2
3 4 {} 1
4 3 {1} 2

Output: [1, 2, 1, 2]

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

Garden Neighbors Used Flowers Assigned Flower
1 2, 4, 3 {} 1
2 1, 3, 4 {1} 2
3 2, 4, 1 {1,2} 3
4 3, 1, 2 {1,2,3} 4

Output: [1, 2, 3, 4]

Complexity Analysis

Measure Complexity Explanation
Time O(n + e) Building the adjacency list takes O(e). Iterating over n gardens and their neighbors is O(n + e).
Space O(n + e) Adjacency list uses O(n + e), and the answer array uses O(n).

The complexity is efficient for the problem constraints (n <= 10^4, paths <= 2*10^4).

Test Cases

# Basic examples
assert Solution().gardenNoAdj(3, [[1,2],[2,3],[3,1]]) in ([1,2,3], [1,2,4], [1,4,2], [3,2,1])
assert Solution().gardenNoAdj(4, [[1,2],[3,4]]) in ([1,2,1,2], [2,1,2,1])
assert Solution().gardenNoAdj(4, [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]) == [1,2,3,4]

# Edge case: no paths
assert Solution().gardenNoAdj(5, []) == [1,1,1,1,1]

# Maximum neighbors (3)
assert Solution().gardenNoAdj(4, [[1,2],[1,3],[1,4]]) in ([1,2,3,4], [1,3,2,4], [1,2,4,3])

# Linear chain
assert Solution().gardenNoAdj(5, [[1,2],[2,3],[3,4],[4,5]]) in ([1,2,1,2,1], [1,