Java - Greedy solution - O(flowerbed) - beats 100%


  • 27

    Greedily place a flower at every vacant spot encountered from left to right!

    public class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            int count = 0;
            for(int i = 0; i < flowerbed.length && count < n; i++) {
                if(flowerbed[i] == 0) {
    	     //get next and prev flower bed slot values. If i lies at the ends the next and prev are considered as 0. 
                   int next = (i == flowerbed.length - 1) ? 0 : flowerbed[i + 1]; 
                   int prev = (i == 0) ? 0 : flowerbed[i - 1];
                   if(next == 0 && prev == 0) {
                       flowerbed[i] = 1;
                       count++;
                   }
                }
            }
            
            return count == n;
        }
    }
    

  • 0

    Will the greedy solution always work? I actually implemented in with DP because each space that is empty can either be set to empty or a plant can be plotted. So if you have [0,0,0,0 ...], there is two possible paths:

    After first plant being plotted

    1. [1,0,0,0, ....]
    2. [0,1,0,0,.....]

    These are two different starting points which can lead to different combination based on the restriction of 2 plants not being able to be plotted adjacently.

    I guess I don't understand why we don't have to account for that aspect with the greedy solution?

    Thanks


  • 4

    You are correct.

    DP will always work for any problem that can be solved by greedy which deals with making local choices while DP considers all global choices. There are many problems where greedy isn't sufficient to get an optimal solution.

    However, this problem isn't one. Here each local choice is enough to get the optimal solution. You can prove it by induction. No matter what other choices you consider, for any given row of plants, you will find that the greedy solution will always yield the optimal solution. The other choices that you traverse here would simply be a waste.


  • 2
    H

    @soumyadeep2007 isn't 'return count >= n'?


  • 3

    @hayden2 In one case, we stop the loop as soon as count becomes equal to n [This is an optimization]. In the other case we stop the loop if the entire flowerbed is traversed(count will definitely be less than n in that case). Thus, there is no case where count can be greater than n, and by extension, checking for count >= n isn't required.


  • 0
    D

    @soumyadeep2007 How do you use induction to prove this? Is there a mathematical way to prove this via induction?

    Assumption: No matter what other choices you consider, for any given row of plants, you will find that the greedy solution will always yield the optimal solution.

    Proof: ?

    Thanks,
    Derek


  • 6

    @dare_wreck54-yahoo-com
    Here's a proof by induction: (Have only shown the inductive step)
    Excuse my poor handwriting!0_1496826095638_proof2_06-07-2017-142904-page-001.jpg


  • 1

    Similar Approach.

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int idx = 0; idx < flowerbed.length && n > 0; idx ++)
            if (flowerbed [idx] == 0 && (idx == 0 || flowerbed [idx - 1] == 0) && (idx == flowerbed.length - 1 || flowerbed [idx + 1] == 0)) {
                n--;
                flowerbed [idx] = 1;
            }
        return n == 0;
    }
    

  • 2

    My solution:

            if(flowerbed == null || flowerbed.length == 0) return false;
            if(n == 0) return true;
            int count = 0;
            for(int i = 0; i < flowerbed.length; i ++){
                if(i == 0 && flowerbed[i] == 0){
                    count ++;
                    flowerbed[i] = 1;
                    continue;
                }
                if(i > 0 && flowerbed[i] == 0 && flowerbed[i - 1] == 0){
                    count ++;
                    flowerbed[i] = 1;
                }
                if(i > 0 && flowerbed[i] == 1 && flowerbed[i - 1] == 1){
                    count --;
                    flowerbed[i - 1] = 0;
                }
            }
            return count >= n;
        }
    

  • 1

    @soumyadeep2007 This exactly what I would like to say. And I think this is why the problem is labeled as easy:-)

    My version:
    Greedy Algorithm: Just count the length of gap (consecutive 0's) and a "plantable" spot will be every other position in a gap.

    NOTE: imagine to pad left and right ends with an extra 0 because each end has only one neighbor.

        bool canPlaceFlowers(vector<int>& flowerbed, int n) {
            flowerbed.push_back(0);
            int gap = 1;
            for (int x : flowerbed) {
                bool plantable = x? (gap=0) : (++gap > 2 && gap%2);
                if ((n-=plantable) <= 0) return true;
            }
            return false;
        }
    

  • 0

    @Tōsaka-Rin You might add to check for early termination when count exceeds n.


  • 2
    A

    @soumyadeep2007 said in Java - Greedy solution - O(flowerbed) - beats 100%:

                   if(next == 0 && prev == 0) ;
    

    when you find a planting location, you can jump the next location (i+=2) and you wont need "flowerbed[i] = 1";. Could be faster.

        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            if (n==0) return true;
            int nn = 0;
            int i=0;
            while (i<flowerbed.length) {
                if (flowerbed[i]==1) i+=2;
                else if ((i==0 || flowerbed[i-1] ==0) && ( i==flowerbed.length-1||flowerbed[i+1] ==0)) {
                    if (++nn==n) return true;
                    i+=2;
                }
                else 
                    i++;
            }
            return false;
        }
    

  • 2

    @dare_wreck54-yahoo-com

    If asking for how many ways to place the flower, DP is a better choice. For this question, greedy is good enough.


  • 1
    L

    Very nice. Had the same greedy solution in mind but I wasn't able to account for all the edge cases as cleanly as you did.


  • 0

    @lekzeey Thanks! :)


  • 0
    J

    @Himanshu I wrote something similar but just adding a case. If we set flowerbed[idx] = 1 then can directly jump to idx + 2 position. Wecan observe the increase in run time.

    public class Solution {
        public boolean canPlaceFlowers(int[] flowerbed, int n) {
            
            for(int idx=0; idx<flowerbed.length && n > 0; idx++)
            {
                if(flowerbed[idx]==0  && (idx == 0 || flowerbed[idx-1]==0) && (idx == flowerbed.length-1 || flowerbed[idx+1]==0))
                {
                    n--; 
                    flowerbed[idx]=1;
                    idx++;
                }
                
            }
            return (n == 0);
            
        }
    }
    

  • 0
    A
    This post is deleted!

Log in to reply
 

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