Can Place Flowers

How it works

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.

Steps

1. Initialize an empty plot counter. If the first cell is empty, start the counter at 1 (treating the left boundary as open).
2. Iterate through each cell in the flowerbed.
3. 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.
4. When encountering an empty cell (0), increment the counter.
5. After the loop, handle the trailing empty sequence using empty/2 (right boundary is open).
6. Return true if we placed at least n flowers.

Complexity

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

Things to watch for

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.

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.

from typing import List

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

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int empty = flowerbed[0] == 0 ? 1 : 0;

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

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