This solution does not modify the original array, solves the problem in place.
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
# In case of invalid input, return False
if n < 0:
return False
if len(flowerbed) == 0:
return n == 0
# Handle case of single flower explicitely so that i + 1 logic in the next
# section of code works, else throws array index out of bound error
if len(flowerbed) == 1:
return (flowerbed[0] == 1 and n == 0) or (flowerbed[0] == 0 and n <= 1)
l = len(flowerbed)
# will store the count of flowers placed so far
placed = 0
# whether we have seen one flower in the previous index or not
prev_seen = False
for i in range(l - 1):
# If current index is flower
if flowerbed[i] == 1:
prev_seen = True
continue
# Reached here means current index is not a flower, we check
# whether previous index was a flower, if yes, we continue but
# also set previously seen as false because for next index, the
# current index will stay empty so we can place a flower in the
# next available index
if prev_seen:
prev_seen = False
continue
# This is an empty location whose previous position is also empty
prev_seen = False
# Check if next position has a flower, then simply move on as
# previous seen will anyway become True in the next iteration
if flowerbed[i + 1] == 1:
continue
# All conditions satisfied, this place can hold a new flower
placed += 1
prev_seen = True
# handle last value explicitely as for loop runs to second last place
if not prev_seen and flowerbed[l - 1] == 0:
placed += 1
# Check for greater than equality, as we might be able to place more
# flowers than n too, similarly we can solve if the question asks for
# exactly n flowers, then check for equality only
return placed >= n