thesarfo

Reference

Can Place Flowers

Checking whether n new flowers can be planted in a flowerbed without any two being adjacent.

views 0

Can n new flowers be planted in a flowerbed (1=occupied, 0=empty) without any two flowers being adjacent? (LeetCode 605)

Approach: for each empty plot, check whether both neighbors (accounting for array edges) are also empty; if so, plant there and count it. Return whether the count reaches n.

public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;


        for (int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 0) {
                boolean emptyLeftPlot = (i == 0) || (flowerbed[i - 1] == 0);
                boolean emptyRightPlot = (i == flowerbed.length - 1) || (flowerbed[i + 1] == 0);


                if (emptyLeftPlot && emptyRightPlot) {
                    flowerbed[i] = 1;
                    count++;


                    if (count >= n) {
                        return true;
                    }
                }
            }
        }


        return count >= n;
    }
}

Time: O(m). Space: O(1).