[Java] O(n) solution Greedy Algorithm


  • 0
    M

    The idea is simple: place the flower as left as possible. Once n drops to 0, it means a successful setup.

        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            if (n == 0) return true;
            for (int i = 0; i < flowerbed.length; i++){
                if (isValid(flowerbed, i)) {
                    flowerbed[i] = 1;
                    n--;
                }
                if (n == 0) return true;    
            }
            return false;
        }
        
        private boolean isValid(int[] nums, int i){
            if (nums[i] == 1)   return false;
            if (i - 1 >= 0 && nums[i - 1] == 1) 
                return false;
            if (i + 1 < nums.length && nums[i + 1] == 1)    
                return false;
            return true;
        }
    

Log in to reply
 

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