# LeetCode 605: Can Place Flowers

## Problem Restatement

We are given a flowerbed represented by a binary array.

| Value | Meaning |
|---|---|
| `0` | Empty plot |
| `1` | A flower is already planted |

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:

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

Input:

| Parameter | Meaning |
|---|---|
| `flowerbed` | Binary array representing plots |
| `n` | Number of new flowers to plant |

Output:

| Type | Meaning |
|---|---|
| `bool` | `True` if we can plant `n` flowers, otherwise `False` |

## Examples

Example 1:

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

We can plant one flower at index `2`:

```text
[1, 0, 1, 0, 1]
```

So the answer is:

```python
True
```

Example 2:

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

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

So the answer is:

```python
False
```

Example 3:

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

We can plant at indices:

```text
0, 2, 4
```

Final flowerbed:

```text
[1, 0, 1, 0, 1]
```

So the answer is:

```python
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:

| Choice | Meaning |
|---|---|
| Plant here | Use the plot |
| Skip here | Leave the plot empty |

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:

```python
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

```python
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:

```python
length = len(flowerbed)
```

Then we scan every position:

```python
for i in range(length):
```

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

```python
if flowerbed[i] == 1:
    continue
```

Next, we check the left side:

```python
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:

```python
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:

```python
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:

```python
if n == 0:
    return True
```

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

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m)` | We scan the array once |
| Space | `O(1)` | Only a few variables are used |

## Alternative Without Modifying Input

Some versions prefer not to modify the original array.

We can keep the same logic while tracking placements separately.

```python
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

```python
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:

| Case | Why |
|---|---|
| Basic valid placement | Confirms core logic |
| Impossible placement | Confirms rejection |
| All empty plots | Checks maximum placement |
| Single-element arrays | Boundary condition |
| Two-element arrays | Adjacent edge handling |