# Can Place Flowers
**Difficulty:** EASY
[External](https://leetcode.com/problems/can-place-flowers)
Canonical: https://scaleengineer.com/dsa/problems/can-place-flowers
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Airbnb](https://scaleengineer.com/companies/airbnb), [Atlassian](https://scaleengineer.com/companies/atlassian), [Cisco](https://scaleengineer.com/companies/cisco), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Yandex](https://scaleengineer.com/companies/yandex), [Nike](https://scaleengineer.com/companies/nike), [SOTI](https://scaleengineer.com/companies/soti)
---
## Problem
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in **adjacent** plots.

Given an integer array `flowerbed` containing `0`'s and `1`'s, where `0` means empty and `1` means not empty, and an integer `n`, return `true` _if_ `n` _new flowers can be planted in the_ `flowerbed` _without violating the no-adjacent-flowers rule and_ `false` _otherwise_.

**Example 1:**

**Input:** flowerbed = [1,0,0,0,1], n = 1
**Output:** true

**Example 2:**

**Input:** flowerbed = [1,0,0,0,1], n = 2
**Output:** false

**Constraints:**

* `1 <= flowerbed.length <= 2 * 104`
* `flowerbed[i]` is `0` or `1`.
* There are no two adjacent flowers in `flowerbed`.
* `0 <= n <= flowerbed.length`

# Approaches
## Single Pass with Array Copy
This approach involves iterating through the flowerbed and checking each empty plot to see if a flower can be planted. To avoid issues with modifying the array while iterating, a copy of the flowerbed is made. We count the total number of new flowers that can be planted and then compare this count with `n`.
**Time:** O(N), where N is the number of plots in the flowerbed. We iterate through the array once. · **Space:** O(N), for the copy of the `flowerbed` array.
**Pros:** Conceptually simple and easy to follow.; Avoids modifying the original input array.
**Cons:** Uses extra space proportional to the size of the input, which is inefficient for large flowerbeds.
### Explanation
The core idea is to simulate the process of planting flowers without altering the original array during the decision-making process for each plot. We create a temporary copy of the `flowerbed` array. Then, we iterate through the flowerbed from left to right. For each empty plot `flowerbed[i] == 0`, we check its neighbors. The neighbors are at `i-1` and `i+1`. We must handle the edge cases where `i` is 0 or the last index. If a plot at index `i` is empty and both its neighbors are also empty (or it's an edge), we can plant a flower there. We increment a counter for planted flowers and update the copy of the array at index `i` to 1. This ensures that when we check the next plot, our decision is based on the updated state of the flowerbed. Finally, we check if the total count of flowers we could plant is greater than or equal to `n`.

```java
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n == 0) {
            return true;
        }
        int[] temp = new int[flowerbed.length];
        System.arraycopy(flowerbed, 0, temp, 0, flowerbed.length);
        
        int count = 0;
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] == 0) {
                // Check previous plot
                boolean prevEmpty = (i == 0) || (temp[i - 1] == 0);
                // Check next plot
                boolean nextEmpty = (i == temp.length - 1) || (temp[i + 1] == 0);
                
                if (prevEmpty && nextEmpty) {
                    temp[i] = 1; // Plant the flower in the copy
                    count++;
                    if (count >= n) {
                        return true;
                    }
                }
            }
        }
        return count >= n;
    }
}
```
### Algorithm
- If `n` is 0, return `true` immediately.
- Create a copy of the `flowerbed` array to avoid modifying the original array while iterating.
- Initialize a counter `count` to 0, which will track the number of flowers planted.
- Iterate through the copied `flowerbed` from the first plot to the last.
- For each plot `i`, if it's empty (`flowerbed[i] == 0`):
  - a. Check if the previous plot is empty. This condition is met if `i` is the first plot (`i == 0`) or if `flowerbed[i - 1] == 0`.
  - b. Check if the next plot is empty. This condition is met if `i` is the last plot (`i == flowerbed.length - 1`) or if `flowerbed[i + 1] == 0`.
  - c. If both neighboring plots are empty, plant a flower by setting `flowerbed[i] = 1` in the copy and increment `count`.
- After planting a flower, check if `count` has reached `n`. If it has, we can stop early and return `true`.
- If the loop completes, return `true` if `count >= n` and `false` otherwise.

## Greedy Single Pass (In-place)
This is an optimized approach that avoids using extra space. We iterate through the flowerbed once, and if we find a valid spot to plant a flower, we 'plant' it by changing the value in the array from 0 to 1. This greedy decision works because planting a flower at the earliest possible spot does not prevent us from achieving the maximum possible number of plantings.
**Time:** O(N), where N is the length of the `flowerbed`. We perform a single pass through the array. · **Space:** O(1), as we are modifying the input array in-place and using only a few extra variables for counting and iteration. No additional space proportional to the input size is required.
**Pros:** Highly efficient in terms of space, using constant extra space.; Efficient in time, requiring only a single pass over the data.; The greedy approach is proven to be correct for this problem and is intuitive.
**Cons:** Modifies the input array, which might be undesirable in some contexts where the original input must be preserved.
### Explanation
The greedy strategy is to iterate through the flowerbed and plant a flower at the first available spot. An available spot at index `i` is one where `flowerbed[i]` is 0, and its adjacent plots (`i-1` and `i+1`) are also 0. We must handle the boundaries carefully: for the first plot (`i=0`), we only need to check the next plot (`i+1`), and for the last plot, we only need to check the previous one (`i-1`).

When we find such a spot, we plant a flower by setting `flowerbed[i] = 1` and increment our count of planted flowers. This modification correctly affects the check for the next plot `i+1`, as its preceding plot is now occupied. We continue this until we have planted `n` flowers (at which point we can return `true` early) or have scanned the entire flowerbed.

```java
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.length; i++) {
            // Check if current plot is available
            if (flowerbed[i] == 0) {
                // Check left and right plots
                boolean emptyLeftPlot = (i == 0) || (flowerbed[i - 1] == 0);
                boolean emptyRightPlot = (i == flowerbed.length - 1) || (flowerbed[i + 1] == 0);
                
                if (emptyLeftPlot && emptyRightPlot) {
                    flowerbed[i] = 1; // Plant flower
                    count++;
                    if (count >= n) {
                        return true;
                    }
                }
            }
        }
        return count >= n;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through the `flowerbed` array from `i = 0` to `length - 1`.
- At each position `i`, check if a flower can be planted:
  - a. The current plot `flowerbed[i]` must be empty (0).
  - b. The previous plot must be empty. This is true if `i` is the first plot (`i == 0`) or `flowerbed[i - 1] == 0`.
  - c. The next plot must be empty. This is true if `i` is the last plot (`i == flowerbed.length - 1`) or `flowerbed[i + 1] == 0`.
- If all three conditions are met, it's a valid spot. Plant a flower by modifying the array (`flowerbed[i] = 1`) and increment `count`.
- After incrementing `count`, check if `count` is already greater than or equal to `n`. If so, we have found enough spots, and we can return `true` immediately.
- If the loop finishes, it means we have checked all plots. We return `true` if we were able to plant at least `n` flowers (`count >= n`), and `false` otherwise.

# Solutions
### Java

```java
class Solution { public boolean canPlaceFlowers ( int [] flowerbed , int n ) { int m = flowerbed . length ; for ( int i = 0 ; i < m ; ++ i ) { int l = i == 0 ? 0 : flowerbed [ i - 1 ]; int r = i == m - 1 ? 0 : flowerbed [ i + 1 ]; if ( l + flowerbed [ i ] + r == 0 ) { flowerbed [ i ] = 1 ; -- n ; } } return n <= 0 ; } }
```

### CPP

```cpp
class Solution { public: bool canPlaceFlowers ( vector < int >& flowerbed , int n ) { int m = flowerbed . size (); for ( int i = 0 ; i < m ; ++ i ) { int l = i == 0 ? 0 : flowerbed [ i - 1 ]; int r = i == m - 1 ? 0 : flowerbed [ i + 1 ]; if ( l + flowerbed [ i ] + r == 0 ) { flowerbed [ i ] = 1 ; -- n ; } } return n <= 0 ; } };
```

### Python

```python
class Solution : def canPlaceFlowers ( self , flowerbed : List [ int ], n : int ) -> bool : flowerbed = [ 0 ] + flowerbed + [ 0 ] for i in range ( 1 , len ( flowerbed ) - 1 ): if sum ( flowerbed [ i - 1 : i + 2 ]) == 0 : flowerbed [ i ] = 1 n -= 1 return n <= 0
```