605. Can Place Flowers¶
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.
Intuition¶
- We can plant a flower if both the adjacent plots are empty
Approach¶
- Iterate over the array checking each plot and surrounding
- If the plot is available for planting decrease the pending flower count and update the plot as planted.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(n)\)$ |
- No extra space is used
- We iterate over the array only once
Code¶
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if(n == 0) return true;
for(int i = 0; i < flowerbed.length; ++i) {
if(flowerbed[i] == 0) {
// check adjacent plots
if( ( i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.length-1 || flowerbed[i+1] == 0)) {
// put flower in the plot and skip the adjacent plot
i++;
// decrease remaining plants
n--;
// if none yes all planted
if(n == 0) return true;
}
}
}
return false;
}
}