# Python, Straightforward with Explanation

• We need to justify a greedy solution.

Call a plot ready if the very first flower is allowed to be planted there.
Consider the left-most ready plot x (if it exists). If x+1 is not ready, then we increase our answer strictly by planting at x, since x does not disturb any ready plots. If x+1 is ready, then planting at x instead of x+1 is atleast as good, since x disturbs only {x, x+1}, whereas x+1 disturbs {x, x+1, x+2}.

Now our implementation is trivial. For each plot from left to right, if we can plant a flower there, then do so. We can plant a flower if the left neighbor is 0 (or we are on the left edge), AND the right neighbor is 0 (or we are on the right edge).

``````def canPlaceFlowers(self, A, N):
for i, x in enumerate(A):
if (not x and (i == 0 or A[i-1] == 0)
and (i == len(A)-1 or A[i+1] == 0)):
N -= 1
A[i] = 1
return N <= 0
``````

• You can have a slight optimization if you include a return for when n<=0 in the if statement.

``````class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
for i,c in enumerate(flowerbed):
if (not c and (i==0 or not flowerbed[i-1])) and (i==len(flowerbed)-1 or not flowerbed[i+1]):
n-=1
flowerbed[i]=1
if n<=0: return True
return not n``````

• More optimized

class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""

``````    max_trees = 0
l = len(flowerbed)
i = 0
while i < l:
if (flowerbed[i] == 0) and ((i == 0) or (flowerbed[i-1] != 1)) and ((i+1 >= l) or (flowerbed[i+1] != 1) ):
max_trees += 1
if max_trees - n >= 0:
return True
i +=2
else:
i += 1

return max_trees >= n``````

• No improvement, but more straight-forward and easier to understand

``````class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
count = 0
flowerbed = [0] + flowerbed + [0]
for i in range(1, len(flowerbed)-1):
if flowerbed[i-1] == flowerbed[i] == flowerbed[i+1] == 0:
flowerbed[i] = 1
count += 1
return count >= n
``````

• Basic idea, if there are x continuous empty slots, you could plant (x-1)/2 flowers at most.

``````class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
cnt=1
po=0
for i in flowerbed:
if i==1:
po+=(cnt-1)/2
cnt=0
else:
cnt+=1
if cnt>1:po+=cnt/2
return po>=n
``````

• @awice sorry i just have a question
what is meant by
if (NOT x and (i == 0 or A[i-1] == 0)
what is the function of NOT x, here? thx

• @JianQiang1029
meaning x == 0

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