# Can Place Flowers

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

• @KUSA Why do you think so?

• @KUSA yes u are right

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

• This post is deleted!

• 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.

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

• 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

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

• 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

• @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;
``````

• 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

• Additional optimization: don't update the array.

• 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``````

• 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) {
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;
}