605. Can Place Flowers (Python)

Related Topic

Array .

Description

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Sample I/O

Example 1

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note

1. The input array won’t violate no-adjacent-flowers rule.
2. The input array size is in the range of [1, 20000].
3. n is a non-negative integer which won’t exceed the input array size.

Methodology

If n is 0, then return true. We wrap 2 available polts to original flowerbed in case if the first plot is available. We iterate the flowerbed. If the current plot is planted then we skip. Otherwise we compare last and next plot. If one of the them are not planted then we plant the flower and update the n, once n reach to 0, return true.

def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
    if n ==0: return True
    flowerbed = [0] + flowerbed + [0]
    size = len(flowerbed)
    for i in range(1, size-1):
        if flowerbed[i]:
            continue
        elif flowerbed[i - 1] == flowerbed[i + 1] == 0:
            n-=1
            flowerbed[i] = 1
            if n == 0:return True
    return False

BigO

We iterate the list once so the total cost will be O(n)