Straightforward Java Solution With Explanation Using Continuous Zeros' Property


  • 0
    X

    By discovery, we can see that if there are 3 continuous zeros, then it can place 1 flower in the middle.
    ex :
    middle: 000 -> 010
    And in the head and tail, we only need 2 continuous zeros to place 1 flower.
    ex:
    head: 001 -> 101
    tail: 100 -> 101

    The following code is O(flowerbeds number).
    I don't optimize it for code's readability.(can use break to jump out of the for loop)

    public class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            // head
            boolean prevIsZero = true;
            int zero_count = 1;
    
            // middle
            for(int val : flowerbed) {
                if(val == 1) {
                    zero_count = 0;
                    prevIsZero = false;
                }
                else if(val == 0) {
                    zero_count ++;
                }
                
                // place the flower
                // 000 -> 010
                if(zero_count == 3) {
                    n --;
                    zero_count = 1;
                }
    
            }
    
            // tail
            if(zero_count == 2)n --;
    
            if(n <= 0)return true;
            else return false;
        }
    }
    

Log in to reply
 

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