# Can Place Flowers LeetCode Solution

Difficulty Level Easy

## Problem Statement

Can Place Flowers LeetCode Solution – 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 if `n` new flowers can be planted in the `flowerbed` without violating the no-adjacent-flowers rule.

## Example

### Input:

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

n = 1

true

## Approach:

Let’s consider a very simple case where we have a bunch of 0s ending with 1.

Example:

01

001

0001

00001

We can plant only in the l = arr.size() – 2 zeros. A total number of plants that can be planted in such a section = Math.ceil(l/2D) Now we can imagine the whole array composed of such partitions.

Example

[1,0,0,0,1]

[1,0] [0,0,1]

Solution: Linearly scan through the array always incrementing the size of the window. Whenever we encounter 1, we calculate the number of plants possible in that subarray.

1. we use two-point `start``end` to record the `i`th empty pilot’s left and right flower position
2. for `i`th pilot, we calculate the distance to the left (`i-start`)and to right(`end-i`) and get the `min distance`
3. if `min distance >=2` we can say that this pilot can be placed as a flower.
4. then we set `i`th pilot as 1, which means that this pilot has been placed and we reset the start point to `i` and `decrement n`
5. if `n==0` which means all flowers have been placed

`Special case`;

1. If the first or last position is `0`, it means that the left or right side has not been spent. At this time we set start or end to `length of the array`, because we need to find the minimum distance between the two sides of the empty position. At this time, the left position and the right position can seem infinitely large.
2. If n=0, it returns true by default.

3. `,1` This case also returns true by default.

## Code for Can Place Flowers

### Java Program

```class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0;
int first = -2;
int second = 0;
while(second < flowerbed.length){
while(second < flowerbed.length && flowerbed[second] != 1){
second ++;
}
if(second >= flowerbed.length){break;}
count += (second-first-2)/2;

first = second;

second ++;
}
System.out.println(second);
count += (second-first-1)/2;
return count >= n;
}
}```

### C++ Program

```class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0 ;
int s = flowerbed.size();
for(int i = 0 ; i < s ; i++ ){
if(flowerbed[i] == 0){      // when a place is
bool leftflag = (i == 0) || (flowerbed[i-1] == 0);  //check whether left is empty
bool rightflag = (i == s-1) || (flowerbed[i+1] == 0); //check whether left is empty

if(leftflag && rightflag){  // updation
flowerbed[i] = 1;
count++;
if(count >= n){
return true;
}
}
}
}
return count>=n;
}
};```

## Complexity Analysis for Can Place Flowers LeetCode Solution

Time Complexity: O(n) as we are just iterating the array once.

Space Complexity: O(1) as we are not using any extra space.

Translate »