Can Place Flowers

Problem

You are given a row of garden plots as an integer array flowerbed, where each entry is 1 (a flower is already planted there) or 0 (the plot is empty). Flowers cannot be planted in adjacent plots — every flower must have empty (or out-of-bounds) plots on both sides. The input already satisfies this rule.

Given an integer n, decide whether it is possible to plant n new flowers in the empty plots without ever violating the no-adjacent-flowers rule. Return True if it is possible, otherwise False.

Examples

• flowerbed = [1,0,0,0,1], n = 1 → True — the middle plot (index 2) has empty neighbors on both sides.
• flowerbed = [1,0,0,0,1], n = 2 → False — planting at index 2 uses up the only legal spot; no second spot remains.
• flowerbed = [0,0,1,0,0], n = 1 → True — index 0 works because the left edge counts as empty.

Constraints

• 1 <= len(flowerbed) <= 2 * 10^4
• flowerbed[i] is 0 or 1, with no two adjacent 1s
• 0 <= n <= len(flowerbed)

With the length capped at 2 * 10^4, aim for a single O(n) pass.

Think about it first

TL;DR

Greedy left-to-right planting — O(n) time, O(1) extra space (O(n) if you avoid mutating the input).

Approach 1 — Brute force (backtracking)

Try every way of placing n flowers: find each currently-legal plot, tentatively plant there, recurse for the remaining n - 1, and undo on failure.

from typing import List


def canPlaceFlowers(flowerbed: List[int], n: int) -> bool:
    if n == 0:
        return True

    def legal(bed: List[int], i: int) -> bool:
        left_empty = i == 0 or bed[i - 1] == 0
        right_empty = i == len(bed) - 1 or bed[i + 1] == 0
        return bed[i] == 0 and left_empty and right_empty

    def place(bed: List[int], remaining: int) -> bool:
        if remaining == 0:
            return True
        for i in range(len(bed)):
            if legal(bed, i):
                bed[i] = 1
                if place(bed, remaining - 1):
                    return True
                bed[i] = 0
        return False

    return place(flowerbed[:], n)

Complexity: O(len^n) time in the worst case, O(len) space. With len up to 2 * 10^4 and n up to len, the branching explodes and the approach is infeasible.

Approach 2 — Greedy single pass

The insight: if a plot is plantable when you reach it scanning left to right, planting there is never worse than skipping it. A flower at position i only blocks positions i - 1 (already behind you and empty, or you couldn’t plant) and i + 1 — and any solution that instead plants at i + 1 blocks i + 2 as well, so it can be swapped to use i without losing anything. This is a classic greedy algorithm: making the locally best choice at each step and never revisiting it, which works here because choices can be exchanged without penalty.

from typing import List


def canPlaceFlowers(flowerbed: List[int], n: int) -> bool:
    bed = flowerbed[:]  # copy so the caller's list is untouched
    count = 0
    for i in range(len(bed)):
        if bed[i] == 0:
            left_empty = i == 0 or bed[i - 1] == 0
            right_empty = i == len(bed) - 1 or bed[i + 1] == 0
            if left_empty and right_empty:
                bed[i] = 1
                count += 1
                if count >= n:
                    return True
    return count >= n

Walkthrough on flowerbed = [1,0,0,0,1], n = 1:

count >= n → return True. For n = 2 the scan finishes with count = 1 → False.

Complexity: O(n) time, O(1) extra space if mutating in place is acceptable (O(n) for the defensive copy).

Approach 3 — Count runs of zeros

The insight: you never need to simulate at all. Between two planted flowers, a run of L consecutive zeros holds exactly (L - 1) // 2 new flowers. Padding a virtual empty plot on each end makes the boundary runs follow the same formula — an edge run then behaves like an interior run one longer.

from typing import List


def canPlaceFlowers(flowerbed: List[int], n: int) -> bool:
    count = 0
    run = 1  # virtual empty plot before the bed
    for plot in flowerbed:
        if plot == 0:
            run += 1
        else:
            count += (run - 1) // 2
            run = 0
    run += 1  # virtual empty plot after the bed
    count += (run - 1) // 2
    return count >= n

Walkthrough on flowerbed = [1,0,0,0,1], n = 1:

• Start run = 1 (virtual left pad). First plot is 1: count += (1 - 1) // 2 = 0, reset run = 0.
• Three zeros: run = 3. Next plot is 1: count += (3 - 1) // 2 = 1, reset run = 0.
• End: run = 0 + 1 = 1 (virtual right pad), count += 0. Total count = 1 >= 1 → True.

Complexity: O(n) time, O(1) space, and the input is never modified.

Common pitfalls

• Forgetting the edges: index 0 and index len - 1 each have only one real neighbor — treat the out-of-bounds side as empty, or you will reject valid plantings like [0,0,1,...].
• Checking neighbors against the original array while planting into a copy — after you plant at i, position i + 1 must see that new flower, so check the array you are mutating.
• Off-by-one in the run formula: a run of L zeros holds (L - 1) // 2 flowers, not L // 2 — try L = 2 (holds 0) and L = 3 (holds 1) to convince yourself.
• Not handling n = 0: the answer is trivially True, and code that only returns inside the loop can miss it.

Pattern takeaway

When placements only interact with their immediate neighbors, a left-to-right greedy is usually optimal: prove an exchange argument (“any solution using a later slot can be rewritten to use this one”), then commit to each local choice in a single pass. The zero-run counting variant shows the same idea one level up — turn a simulation into arithmetic over maximal segments.