Can Place Flowers


  • 0

    Click here to see the full article post


  • 0
    H

    I really don't think this is a easy problem.....The next two questions are easier!


  • 0

    @KUSA Why do you think so?


  • 0
    C

    @KUSA yes u are right


  • 0
    C

    Counting zeros approach also takes O(n) time complexity and seems to be faster because there is not so many comparisons.


  • 0
    This post is deleted!

  • 0
    E

    Editoral is clean and easy to understand. One optimization: when you plant a flower, you can increment i by 2 (you can never plant two beside each other).

    In my solution I added flowers from both the start and end of array during each loop iteration - same worse case scenario but better for some input arrays.


  • 0

    @emilieroberts Thanks for your suggestion. I have updated #2 code accordingly.


  • 0
    X

    If we view the array as a bunch of zeros segmented by 1s (boundaries),
    using the index of these boundary, we would know how many 0s are between boundaries, and can easily calculate the number of flowers that can be put in each segment
    this is much faster than comparing left and right


  • 0
    X

    One optimization: if (flowerbed.length / 2 + 1 < n) return false;
    Is it correct?


  • 0
    K

    for further optimization we could increment the iterator "i" by 2(can be done for while loop not for loop) every time we plant a flower as we know for sure that the subsequent place cannot be planted


  • 0
    W

    @xpfxzxc

    consider following case:

    n = 2, len = 2  
    then 
    len / 2 + 1 = 2 = n
    

    your idea can be better represent in this way:

    if (flowerbed.length < n * 2 - 1) return false;
    

  • 0
    A

    class Solution:
    def canPlaceFlowers(self, flowerbed, n):
    a = [1,0]+flowerbed+[0,1]
    nmax, c = 0, -1
    for v in a:
    if v==0:
    c += 1
    else:
    if c>0: nmax += c//2
    c = -1
    return n <= nmax


  • 0
    M

    Additional optimization: don't update the array.


  • 0
    P

    Both answers modify the input array. I don't think that should be allowed. Here is my solution.

    class Solution(object):
    def canPlaceFlowers(self, flowerbed, n):
    """
    :type flowerbed: List[int]
    :type n: int
    :rtype: bool
    """
    if not flowerbed:
    return False
    if n ==0:
    return True
    spots = 0
    length = len(flowerbed)-1
    i=0
    while i <= length:
    spot_found = False

            if not flowerbed[i]==0:
                i+=1
                continue
            elif i==0:
                if i+1 <=length:
                    if flowerbed[i+1]==0:
                        spot_found = True
                else:
                    spot_found = True
            elif i==length:
                if not i-1 < 0:
                    if flowerbed[i-1] == 0:
                        spot_found = True
                else:
                    spot_found = True
            else:
                if flowerbed[i-1] == flowerbed[i+1] == 0:
                    spot_found = True
            
            if spot_found:
                spots+=1
                i+=2 # go to the next possible spot. Reserve this one
                if spots>=n:
                    return True                
            else:
                i+=1 #go to the next possible spot. 
            
        return False

  • 0

    For the inputs [0] and 2, the online judge gives the following "Expected answer":

    Line 6: bool Solution::canPlaceFlowers(std::vector<int>&, int): Assertion `n <= (int)flowerbed.size() && n >= 0 && (int)flowerbed.size() > 0' failed.

    Given the constraint where the input is not allowed to be modified, here's my Java solution:

    class Solution {
        public boolean canPlaceFlowers(int[] flowerBed, int numFlowersToAdd) {
            if(numFlowersToAdd == 0) {
                return true;
            }
            if(numFlowersToAdd < 0 || flowerBed == null || flowerBed.length == 0) {
                return false;
            }
            int maxFlowersCanPlant = 0;
            int firstZeroIndex = -1; // Index of the last zero we've found
            boolean foundZero = flowerBed[0] == 0 ? true : false;
            for(int i=1; i<flowerBed.length; i++) {
                if(flowerBed[i] == 0) {
                    if(!foundZero) {
                        firstZeroIndex = i;
                    }
                    foundZero = true;
                } else { // We found a 1
                    if(foundZero) {
                        maxFlowersCanPlant += (i-firstZeroIndex-1)/2;
                    }
                    foundZero = false;
                }
            }
            // There are trailing zeros
            if(firstZeroIndex < flowerBed.length && flowerBed[flowerBed.length-1] == 0) {
                firstZeroIndex--;
                maxFlowersCanPlant += (flowerBed.length-firstZeroIndex-1)/2;
            }
            return maxFlowersCanPlant >= numFlowersToAdd;
        }
    }
    

Log in to reply
 

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