605. Can Place Flowers

#array

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