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);
                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
                    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.