Can Place Flowers is a good test of whether you can make a greedy choice and handle array boundaries without a pile of special cases.
A flowerbed is an array of 0s and 1s, where 1 means planted. No two flowers may be adjacent. Can you plant n new flowers?
Scan left to right and plant in every empty spot whose neighbors are both empty. Planting as early as possible never hurts: a flower at position i only blocks i+1, and any solution that skipped i could shift its next flower left to i.
def can_place_flowers(bed, n):
padded = [0] + bed + [0]
for i in range(1, len(padded) - 1):
if padded[i - 1] == padded[i] == padded[i + 1] == 0:
padded[i] = 1
n -= 1
if n <= 0:
return True
return n <= 0
Padding both ends with 0 removes the boundary checks. If the interviewer wants O(1) extra space, check i == 0 or bed[i-1] == 0 and the mirror condition at the right end instead.
You can also count runs of zeros. An interior run of length k fits (k - 1) // 2 flowers, and a run touching an edge fits k // 2. It is a nice second answer to show you understand why the greedy works.
n = 0 is always true.[0] with n = 1 is true.n hits zero.I work on an AI interview copilot at Linkjob AI; this note is part of the practice set we use.