605. Can Place Flowers - Explanation

1. Iteration - I

Intuition

A flower can be planted at position i only if positions i-1, i, and i+1 are all empty. To handle edge cases at the boundaries, we pad the flowerbed with zeros at both ends. This way, we can apply the same rule uniformly across all positions without special boundary checks.

Algorithm

Create a new array with a 0 prepended and appended to the original flowerbed.
Iterate through the padded array from index 1 to length-2 (the original positions).
For each position, check if the current cell and both neighbors are empty (all zeros).
If so, plant a flower by setting the current cell to 1, and decrement n.
After processing all positions, return true if n is 0 or less (we placed enough flowers).

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        f = [0] + flowerbed + [0]

        for i in range(1, len(f) - 1):
            if f[i - 1] == 0 and f[i] == 0 and f[i + 1] == 0:
                f[i] = 1
                n -= 1

        return n <= 0

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Iteration - II

Intuition

Instead of checking each position individually, we can count consecutive empty plots between flowers. For a sequence of k empty plots between two flowers, we can plant (k-1)/2 flowers. At the beginning and end of the flowerbed, the formula differs slightly since there is no blocking flower on one side: we can plant k/2 flowers at the edges.

Algorithm

Initialize an empty plot counter. If the first cell is empty, start the counter at 1 (treating the left boundary as open).
Iterate through each cell in the flowerbed.
When encountering a flower (1), calculate how many new flowers can fit in the empty sequence before it using (empty-1)/2, then reset the counter.
When encountering an empty cell (0), increment the counter.
After the loop, handle the trailing empty sequence using empty/2 (right boundary is open).
Return true if we placed at least n flowers.

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        empty = 0 if flowerbed[0] else 1

        for f in flowerbed:
            if f:
                n -= int((empty - 1) / 2)
                empty = 0
            else:
                empty += 1

        n -= empty // 2
        return n <= 0

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Mark Planted Flowers

After deciding to plant a flower at position i, you must update the flowerbed to reflect the new flower. Otherwise, you may count overlapping positions as valid.

# Wrong: not updating the flowerbed after planting
if f[i-1] == 0 and f[i] == 0 and f[i+1] == 0:
    n -= 1  # Missing: f[i] = 1

Off-by-One Errors at Boundaries

When not padding the array, forgetting to handle the first and last positions specially leads to index-out-of-bounds errors or incorrect neighbor checks.