Java recursive solution with memoization


  • 0

    Must memoize or you will encounter stack overflow on larger test cases.

    public class Solution {
        
        int[] fb;
        int start = 0;
        int size = 0;
        int howMany = 0;
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            fb = flowerbed;
            size = fb.length;
            howMany = n;
            if(flowerbed.length == 1 && flowerbed[0] == 0){
                return true;
            }
            if(fb[0] == 0){
                if(fb[1] == 0){
                    start =start+2;
                    howMany = howMany-1;
                    return help();
                }else{
                    start = start+1;
                    return help();
                }
                // return fb[1] == 0 ? help(n-1, 2, fb.length) : help(n,1,fb.length);
            }else{
                start = start+1;
                return help();
                // return help(n,1,fb.length);
            }
            // return help(n, 0, flowerbed.length);
        }
        
        private boolean help(){
            if(howMany <= 0) return true;
            if(start >= size) return false;
            
            // check if start is 0, 
                // if true check if start +1 && start -1 is zero
                    // true subtract 1 from n, recurse with start +2
                    // false recurse from start+2
                // if false recurse increment to start +1
            
            if(fb[start] == 0){
                if(start+1 < size){
                    if (fb[start+1] == 0 && fb[start-1] == 0){
                        fb[start] = 1;
                        howMany = howMany-1;
                        start = start+2;
                        // return help(n-1, start+2, size);
                        return help();
                    }else{
                        start = start+1;
                        return help();
                        // return help(n,start+1,size);
                    }
                }else{// at end
                    if(fb[start-1] == 0){
                        howMany = howMany-1;
                        start = start+2;
                        return help();
                    }
                        // return help(n-1,start+2,size);
                    else{
                        start = start+2;
                        return help();
                    }
                        // return help(n, start+2, size);
                }
            }else{
                start = start+1;
                return help();
                // return help(n, start+1, size);
            }
            
        }
    }
    

Log in to reply
 

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