Plant a flower wherever both neighbours are empty, scanning left to right. Planting early never hurts, so stop as soon as n fit.
▼The problem
LeetCode 605 (Easy). A flowerbed is an array of 0s (empty) and 1s (planted); flowers can't be in adjacent plots. Return true if n new flowers can be planted without breaking that rule.
Examples (LeetCode's): [1,0,0,0,1], n = 1 → true (plot 2 is the only plot with empty neighbours on both sides; walked in scene 2) and n = 2 → false.
The solution
def can_place_flowers(flowerbed, n):
count = 0
for i in range(len(flowerbed)):
left = i == 0 or flowerbed[i - 1] == 0
right = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
if flowerbed[i] == 0 and left and right:
flowerbed[i] = 1
count += 1
if count >= n:
return True
return count >= nTranscript
Can Place Flowers. A flowerbed is a row of plots: zero means empty, one means planted. No two flowers can sit in neighboring plots. Can you plant n more?
Take one, zero, zero, zero, one, with n equal to one. Plot one sits next to a flower. Plot two has empty plots on both sides, so plant it: true. Ask for two, and there's no room left: false.
The slow way: try every set of empty plots, and check that no two flowers touch. With k empty plots, that's two to the k sets.
The key idea: walk left to right, and plant whenever a plot and both its neighbors are empty. Past either end counts as empty. Planting early never hurts: a flower here only blocks the next plot, and any later choice would block it too. It rhymes with House Robber's no two adjacent rule, but greedy is enough here.
In code, count from zero. For each plot, check the left and right neighbors, treating the ends as empty. If all three are free, plant it and count it. Once the count reaches n, return true.
Now zero, zero, one, zero, zero, with n equal to two. Plot zero is open to the edge: plant, count one. Plot one now touches it. Plot two is taken, and plot three touches it. Plot four is free to the end: plant, count two. True.
One pass over the bed: linear time, and constant extra space.
Look both ways, plant early, stop at n. That's Can Place Flowers.