# LeetCode Notes: Can Place Flowers

## Question

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

**Analysis:**

- First of all, we can find a rule. The zeros on the both sides of the array are different from the zeros between the two
`1`

, and the corresponding rules for the number of flowers that can be planted are different.

Looking for patterns

- The number of 0 in the middle is converted into the number of flowers that can be planted:

The situation when a small amount of 0 is manually calculated

The number of 0 | The number of flowers that can be planted |
---|---|

0 | 0 |

1 | 0 |

2 | 0 |

3 | 1 |

4 | 1 |

5 | 2 |

6 | 2 |

7 | 3 |

8 | 3 |

9 | 4 |

After trying, it is determined that the relationship between the number n of 0 and the number of flowers that can be planted is `Math.floor((n-1) / 2)`

, paste the following code into the console and run it to verify the result:

```
var a = `
0-0
1-0
2-0
3-1
4-1
5-2
6-2
7-3
8-3
9-4`;
function get(n) {
console.log(Math.floor((n - 1) / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
```

- The number of 0 on both sides is converted into the number of flowers that can be planted:

The situation when a small amount of 0 is manually calculated

The number of 0 | The number of flowers that can be planted |
---|---|

0 | 0 |

1 | 0 |

2 | 1 |

3 | 1 |

4 | 2 |

5 | 2 |

6 | 3 |

7 | 3 |

8 | 4 |

9 | 4 |

After trying, it is determined that the relationship between the number n of 0 and the number of flowers that can be planted is `Math.floor(n / 2)`

, paste the following code into the console and run it to verify the result:

```
var a = `
0-0
1-0
2-1
3-1
4-2
5-2
6-3
7-3
8-4
9-4`;
function get(n) {
console.log(Math.floor(n / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
```

- With these two rules, next we need to find the combination of 0 on both sides and 0 in the middle of the array, calculate and transform them respectively, and then calculate the sum
- After testing, it is found that there is a special case - all 0. At this time we choose to deal with it separately, as above, we observe the rule that the array is all 0

- The number of all 0s is converted into the number of flowers that can be planted:

The situation when a small amount of 0 is manually calculated

The number of 0 | The number of flowers that can be planted |
---|---|

0 | 0 |

1 | 1 |

2 | 1 |

3 | 2 |

4 | 2 |

5 | 3 |

6 | 3 |

7 | 4 |

8 | 4 |

9 | 5 |

After trying, it is determined that the relationship between the number n of 0 and the number of flowers that can be planted is `Math.floor((n + 1) / 2)`

, paste the following code into the console and run it to verify the result:

```
var a = `
0-0
1-1
2-1
3-2
4-2
5-3
6-3
7-4
8-4
9-5`;
function get(n) {
console.log(Math.floor((n + 1) / 2));
}
get(0);
get(1);
get(2);
get(3);
get(4);
get(5);
get(6);
get(7);
get(8);
get(9);
```

**Code:**

```
/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function (flowerbed, n) {
// The code commented out below is the original logical division of the 0 in the middle and the 0 on both sides. It is found to be more redundant. Directly use join+split to quickly combine the adjacent 0s. The method is more concise
// // The position of the leftmost 1
// const index = flowerbed.indexOf(1)
// // The position of the rightmost 1
// const lastIndex = flowerbed.lastIndexOf(1)
// // Intercept all 0s to the left of the leftmost 1
// const before = flowerbed.slice(0,index)
// // Intercept the number in the middle of the both sides 1
// const middle = flowerbed.slice(index,lastIndex + 1)
// // Intercept all 0s to the right of the rightmost 1
// const after = flowerbed.slice(lastIndex + 1)
// Count the total number of flowers allowed
let sum = 0;
// Adjacent 0s are combined together to form an array
const zeroArray = flowerbed.join("").split("1");
// In special cases, the original array is only composed of 0, and the number of flowers allowed to be planted can be directly judged
if (zeroArray.length === 1) {
return getFlowersAll(zeroArray[0].length) >= n;
}
// Get all 0s to the left of the leftmost 1
const startZero = zeroArray.shift();
// Intercept all 0s to the right of the rightmost 1
const endZero = zeroArray.pop();
// Count the number of 0 on the left of the leftmost 1 corresponds to the number of flowers that can be planted
if (startZero !== "") {
sum += getFlowersSide(startZero.length);
}
// Count the number of 0 on the right of the rightmost 1 corresponds to the number of flowers that can be planted
if (endZero !== "") {
sum += getFlowersSide(endZero.length);
}
// The remaining 0 number in the middle corresponds to the number of flowers that can be planted
zeroArray.forEach((item, i) => {
sum += getFlowersMiddle(item.length);
});
// return result
return sum >= n;
/**
The number of 0 in the middle is converted into the number of flowers that can be planted
*/
function getFlowersMiddle(n) {
return Math.floor((n - 1) / 2);
}
/**
The number of 0 on both sides is converted into the number of flowers that can be planted
*/
function getFlowersSide(n) {
return Math.floor(n / 2);
}
/**
The number of all 0s is converted into the number of flowers that can be planted
*/
function getFlowersAll(n) {
return Math.floor((n + 1) / 2);
}
};
```

## Comments