605. Can Place Flowers

id: 605 title: Can Place Flowers tags:

• greedy
• array

# Question

Given an integer array flowerbed containing 0s (empty) and 1s (planted), and an integer n, return true if n new flowers can be planted without violating the rule that no two flowers can be planted in adjacent plots.

# Solution

# Pattern

Greedy Approach Iterate through the array and plant a flower at the very first valid empty spot you find. The greedy choice is always optimal here because placing a flower as early as possible maximizes the remaining space for future flowers.

# How to Identify

• The problem asks for a maximum threshold, capacity, or "can we fit $X$" condition.
• The constraint strictly looks at immediate local neighbors (adjacencies).
• Making a localized choice does not negatively impact upstream choices (no backtracking required).

# Description

Step-by-step explanation:

1. Guard Clauses: If $n = 0$, return true immediately. If the array is empty, return false.
2. Linear Scan: Iterate through each plot in the flowerbed array.
3. Skip Planted: If the current plot is already 1, simply move to the next plot.
4. Check Boundaries/Neighbors: If the current plot is 0, check its left and right neighbors.
   • A neighbor is considered valid/empty if it is 0 OR if the current plot is at the physical edge of the array (index 0 or length - 1).
5. Plant and Decrement: If both neighbors are valid, plant a flower (set flowerbed[i] = 1) and decrement $n$.
6. Early Exit: Immediately check if $n \le 0$. If so, return true right away to avoid traversing the rest of the array.
7. Final Check: If the loop finishes and we haven't returned, we check if $n \le 0$ to return the final boolean result.

# The Intuition

Think of this like filling seats in a movie theater where strangers refuse to sit directly next to each other. To maximize the number of people you can seat, you should always tell the next person to sit in the very first available valid seat. Leaving a valid seat empty in hopes of finding a "better" configuration later will only ever decrease or maintain your capacity, it will never increase it.

# Complexity

# Time Complexity

We traverse the array of size $N$ at most once. Operations inside the loop take constant $O(1)$ time. With the early exit, best-case time complexity is $O(1)$ if $n$ is small and placed early.

# Space Complexity

We only allocate a few primitive boolean variables. The array is modified in place, resulting in $O(1)$ auxiliary space.

# Code

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) return true;
        
        for (int i = 0; i < flowerbed.length; i++) {
            // Only attempt to plant if the current spot is empty
            if (flowerbed[i] == 0) {
                boolean leftEmpty = (i == 0 || flowerbed[i - 1] == 0);
                boolean rightEmpty = (i == flowerbed.length - 1 || flowerbed[i + 1] == 0);
                
                if (leftEmpty && rightEmpty) {
                    flowerbed[i] = 1; // Plant
                    n--; // One less flower to plant
                    
                    if (n <= 0) return true; // Early exit
                }
            }
        }
        
        return n <= 0;
    }
}

# Caveats

• Input Mutation: Mutating the flowerbed array is technically a side-effect. In a strictly functional or concurrent production environment, modifying the input parameters is dangerous.
• Read-Only Alternative: To avoid mutation, if you plant a flower at i, you mathematically know i+1 becomes invalid. You can leave the array unmodified and simply do i++ (skip the next index entirely) after decrementing $n$.

# Concepts to Think About

• Greedy Choice Property: Proving that the greedy choice works is key. If you have 0, 0, 0, planting at the middle yields 1 flower (0, 1, 0). Planting at the first yields 2 flowers (1, 0, 1). Greedily picking the earliest valid spot is mathematically guaranteed to yield $\ge$ flowers than skipping it.
• Index Out of Bounds: Using logical short-circuiting (i == 0 || flowerbed[i-1] == 0) safely prevents ArrayIndexOutOfBoundsException without needing clunky nested if statements.

# Logical Follow-up

Question: What if the flowerbed is circular? Meaning the last element and the first element are considered adjacent. Solution: A circular array breaks the simple linear greedy approach because planting at index 0 restricts index n-1, and vice-versa. To solve this, you can run the standard linear greedy algorithm twice:

1. Assume we plant at index 0 (if valid), which means we cannot plant at n-1. Run the greedy approach from index 2 to n-2.
2. Assume we DO NOT plant at index 0. Run the greedy approach from index 1 to n-1. Return the maximum flowers planted between the two scenarios. This maintains $O(N)$ time and $O(1)$ space.