Java classic divide and conquer solution


  • 0

    Plant one seed as soon as possible and leave the rest to sub problem.

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
            return canPlaceFlowers(flowerbed, 0, n);
        }
        
        public boolean canPlaceFlowers(int[] flowerbed, int cur, int n){
            if(n==0) return true;  // planted all seeds
            if(n>(flowerbed.length-cur+1)/2) return false; // not enough slots
            if(flowerbed[cur] == 1){ // this spot is not empty so we can not plant in next slot
                return canPlaceFlowers(flowerbed, cur+2, n);
            }else{
                int prev = cur==0? 0:flowerbed[cur-1];
                int next = cur==flowerbed.length-1? 0: flowerbed[cur+1];
                if(prev == 0 && next ==0){  // right place to plant a seed
                    flowerbed[cur]=1;
                    return canPlaceFlowers(flowerbed, cur+2, n-1);
                }else{ // try to place at next spot
                    return canPlaceFlowers(flowerbed, cur+1, n);
                }
            }
        }
    

Log in to reply
 

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