Can Place Flowers (LeetCode 605): A Greedy Scan With Padding

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.

Problem

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?

Greedy idea

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.

Counting version

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.

Edge cases

I work on an AI interview copilot at Linkjob AI; this note is part of the practice set we use.