LeetCode 605: Can Place Flowers

Problem Restatement

We are given a flowerbed represented by a binary array.

Flowers cannot be planted in adjacent plots.

We are also given an integer n.

We need to determine whether it is possible to plant n new flowers in the flowerbed without violating the no-adjacent-flowers rule.

The official problem states that no two flowers can be planted in adjacent plots and asks whether n new flowers can be planted.

Input and Output

Function signature:

def canPlaceFlowers(flowerbed: list[int], n: int) -> bool:
    ...

Input:

Output:

Examples

Example 1:

flowerbed = [1, 0, 0, 0, 1]
n = 1

We can plant one flower at index 2:

[1, 0, 1, 0, 1]

So the answer is:

True

Example 2:

flowerbed = [1, 0, 0, 0, 1]
n = 2

After planting at index 2, no more valid positions remain.

So the answer is:

False

Example 3:

flowerbed = [0, 0, 0, 0, 0]
n = 3

We can plant at indices:

0, 2, 4

Final flowerbed:

[1, 0, 1, 0, 1]

So the answer is:

True

First Thought: Try Every Combination

One possible approach is to try all possible ways to place flowers and check whether any arrangement works.

This quickly becomes expensive because each empty plot creates another decision:

That creates exponential branching.

We need something simpler.

Key Insight

A flower should always be planted as early as possible whenever it is safe.

Suppose we are at index i.

We can plant a flower there if:

1. The current plot is empty.
2. The left neighbor is empty or does not exist.
3. The right neighbor is empty or does not exist.

That condition is:

flowerbed[i] == 0
and left_is_empty
and right_is_empty

If planting is allowed, planting immediately is always safe because planting later never creates more available space.

This leads to a greedy solution.

Algorithm

Scan the array from left to right.

For each position:

1. Check whether the current plot is empty.
2. Check whether the left side is safe.
3. Check whether the right side is safe.
4. If all conditions are satisfied:
   • Plant a flower.
   • Decrease n.
5. If n becomes 0, return True.

After the scan finishes:

• Return whether n <= 0.

Implementation

class Solution:
    def canPlaceFlowers(self, flowerbed: list[int], n: int) -> bool:
        length = len(flowerbed)

        for i in range(length):

            if flowerbed[i] == 1:
                continue

            left_empty = (i == 0 or flowerbed[i - 1] == 0)
            right_empty = (i == length - 1 or flowerbed[i + 1] == 0)

            if left_empty and right_empty:
                flowerbed[i] = 1
                n -= 1

                if n == 0:
                    return True

        return n <= 0

Code Explanation

We first store the array length:

length = len(flowerbed)

Then we scan every position:

for i in range(length):

If the current plot already contains a flower, we skip it:

if flowerbed[i] == 1:
    continue

Next, we check the left side:

left_empty = (i == 0 or flowerbed[i - 1] == 0)

The first plot has no left neighbor, so it is automatically safe.

We also check the right side:

right_empty = (i == length - 1 or flowerbed[i + 1] == 0)

The last plot has no right neighbor, so it is automatically safe.

If both sides are safe, we plant a flower:

if left_empty and right_empty:
    flowerbed[i] = 1
    n -= 1

We update the flowerbed immediately so later positions see the new flower.

If all required flowers are planted, we return early:

if n == 0:
    return True

At the end, we return whether enough flowers were planted:

return n <= 0

Correctness

The algorithm scans the flowerbed from left to right.

At each position, it plants a flower exactly when doing so does not violate the adjacency rule. Therefore, every planted flower is valid.

Now consider any position where the algorithm plants a flower. Planting there cannot reduce the total number of flowers that can eventually be planted.

Why?

Because if a position is valid now, delaying the placement cannot create additional free neighboring plots later. The current position already blocks at most its two neighbors. Any future flower placement would face the same restriction.

Therefore, planting greedily as early as possible never harms the optimal solution.

The algorithm plants a flower at every valid earliest position. So if the algorithm cannot plant n flowers, then no valid arrangement can.

Therefore, the algorithm returns True exactly when it is possible to plant n flowers.

Complexity

Let m be the length of the flowerbed.

Alternative Without Modifying Input

Some versions prefer not to modify the original array.

We can keep the same logic while tracking placements separately.

class Solution:
    def canPlaceFlowers(self, flowerbed: list[int], n: int) -> bool:
        count = 0
        length = len(flowerbed)

        for i in range(length):

            if flowerbed[i] == 1:
                continue

            left_empty = (i == 0 or flowerbed[i - 1] == 0)
            right_empty = (
                i == length - 1
                or flowerbed[i + 1] == 0
            )

            if left_empty and right_empty:
                count += 1
                flowerbed[i] = 1

        return count >= n

This still updates the array internally, but it separates the planted count from the input parameter n.

Testing

def run_tests():
    s = Solution()

    assert s.canPlaceFlowers([1, 0, 0, 0, 1], 1) is True
    assert s.canPlaceFlowers([1, 0, 0, 0, 1], 2) is False
    assert s.canPlaceFlowers([0, 0, 0, 0, 0], 3) is True
    assert s.canPlaceFlowers([1], 0) is True
    assert s.canPlaceFlowers([0], 1) is True
    assert s.canPlaceFlowers([1], 1) is False
    assert s.canPlaceFlowers([0, 0], 1) is True
    assert s.canPlaceFlowers([0, 0], 2) is False

    print("all tests passed")

run_tests()

Test coverage: