Java O(n) solution


  • 0
    V
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
            
            int i = 0;
            int j = flowerbed.length - 1;
            int sum = 0;
            while (i < flowerbed.length && flowerbed[i] == 0) {
                i += 1;
            }
            if (i == flowerbed.length) {
                sum = (i + 1) / 2;
            } else {
                while (flowerbed[j] == 0) {
                    j -= 1;
                }
                sum += i / 2 + (flowerbed.length - 1 - j) / 2;
            }
            int count = 0;
            while (i < j) {
                if (flowerbed[i] == 0) {
                    count += 1;
                } else {
                    sum += (count - 1) / 2;
                    count = 0;
                }
                i += 1;
                if (i == j) {
                    sum += (count - 1) / 2; 
                }
            }
            return sum >= n;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.