# 605. Can Place Flowers

## How to add boundary elements to reduce code

·

### Problem statement

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.

#### 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 * 10^4`.

• `flowerbed[i]` is `0` or `1`.

• There are no two adjacent flowers in `flowerbed`.

• `0 <= n <= flowerbed.length`.

### Solution: Check the no-adjacent-flowers rule

A new flower can be planted at the position `i` only if

``````flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0.
``````

If the condition is satisfied, the flower can be planted at the position `i`. `flowerbed[i]` is now assigned to `1`. Then you can skip checking the rule for the position `i + 1` and go directly to the position `i + 2`.

#### Code

``````#include <iostream>
#include <vector>
using namespace std;
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
if (n == 0) {
return true;
}
flowerbed.insert(flowerbed.begin(), 0);
flowerbed.push_back(0);
int i = 1;
while (i < flowerbed.size() - 1) {
if (flowerbed[i - 1] == 0 && flowerbed[i] == 0 && flowerbed[i + 1] == 0) {
flowerbed[i] = 1;
n--;
i+=2;
} else {
i++;
}
}
return false;
}
int main() {
vector<int> flowerbed{1,0,0,0,1};
cout << canPlaceFlowers(flowerbed, 1) << endl;
flowerbed = {1,0,0,0,1};
cout << canPlaceFlowers(flowerbed, 2) << endl;
}
``````
``````Output:
1
0
``````

#### Complexity

• Runtime: `O(N)`, where `N = flowerbed.length`.

• Extra space: `O(1)`.

### Implementation note

• In this implementation, you could insert an element `0` to the front and the back of the vector `flowerbed` to avoid writing extra code for checking the no-adjacent-flowers rule at `i = 0` and `i = flowerbed.size() - 1`.

• There are a few ways to insert an element into a vector. Here you can see an example of using the methods `insert` and `push_back` of a `std::vector`.

What is your approach? The problem was picked from leetcode.com. You can submit your solution in any programming language and check the performance.

Thanks for reading. Feel free to share your thought about my content and check out my FREE book 10 Classic Coding Challenges.