Can Place Flowers
Can Place Flowers: given a flowerbed where 1 marks a planted plot and 0 an empty one, decide whether n new flowers can be planted without any two adjacent.
- 1 <= flowerbed.length <= 2 * 10⁴
- flowerbed[i] is 0 or 1
- There are no two adjacent flowers in flowerbed.
- 0 <= n <= flowerbed.length
Intuition
Scan left to right and plant the moment it is legal — a plot is available when it is empty and both neighbours are empty too. Planting as early as possible never blocks a later opportunity, because a flower placed further right would rule out at least as many plots. That greedy choice is safe, so one pass suffices.
A greedy scan is justified whenever an exchange argument shows the earliest valid choice is never worse than deferring. The tell here is a local constraint — no two adjacent — with a global count to satisfy. The same reasoning drives Jump Game, Non-overlapping Intervals, and Assign Cookies.
Approach
Before reading on: convince yourself that planting at the first legal plot never costs you a later one. Then work out how to treat the two ends, where one neighbour does not exist. Aim for O(m) with O(1) space.
The legality test, including the two ends
A plot i can take a flower when flowerbed[i] == 0, the plot to its left is empty, and the plot to its right is empty. The ends need care: index 0 has no left neighbour and the last index has no right neighbour, and a missing neighbour should be treated as empty rather than as blocking. Writing left = flowerbed[i-1] if i > 0 else 0 and the mirror for the right handles both without a separate branch, and avoids the off-by-one that plagues this problem.
Why planting greedily is optimal
Suppose the earliest legal plot is i. Any valid arrangement that skips i must place its next flower at i + 2 or later. Swapping that flower back to i keeps the arrangement valid — i was legal by assumption, and vacating the later plot only frees space. So there is always an optimal solution that plants at i, which means the greedy choice never costs anything. This exchange argument is what licenses a single left-to-right pass instead of any search.
Counting and exiting early
Each time a flower is planted, set that plot to 1 so subsequent legality checks see it — forgetting this write is the classic bug, producing two adjacent flowers. Increment the counter and, as soon as it reaches n, return true immediately; there is no need to finish the scan. If the loop completes, return whether the count reached n. Time is O(m) over the flowerbed with O(1) extra space, mutating the input in place.
Solution & live demo
Common pitfalls
Not marking the plot as planted
if left == 0 and right == 0:
planted += 1if left == 0 and right == 0:
flowerbed[i] = 1
planted += 1Without the write, the next index still sees an empty left neighbour and plants again — producing two adjacent flowers and an inflated count. On [0,0,0] it would wrongly report three.
Reading neighbours without bounds guards
if flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
left = flowerbed[i - 1] if i > 0 else 0 right = flowerbed[i + 1] if i < len(flowerbed) - 1 else 0
At the last index i+1 is out of range, and at index 0 Python's flowerbed[-1] silently reads the last element — a wrong answer rather than a crash, which makes it hard to spot.
Comparing with == instead of >=
return planted == n
return planted >= n
The early return can leave planted exactly at n, but if the loop finishes naturally the count may exceed n on some paths. Asking whether at least n fit is what the question means.
Edge cases
Nothing needs planting, so the answer is true before any scanning matters.
Both neighbours are treated as empty, so one flower fits.
Index 0 has no left neighbour; treating it as empty allows the plant.
The middle plot is blocked on both sides, so nothing can be planted.
Flowers land at indices 0, 2, and 4 — the greedy spacing gives the maximum three.