605_Can Place Flowers

605. Can Place Flowers

Level: easy

Tag: array

Question

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.

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

Idea

Important trick: add 0 at the beginning and in the end of flowerbed. This action won't change if the first and last plot can plant flower.

Scan every plot in the original flowerbed, if it's empty, the plot on the left is empty and the plot on the right is also empty, then this plot can plant flower.

Count how many plots can plant flowers, and compare with n.

.

Complexity

• Time:$O(n)$

• Space:$O(1)$

Solution

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

        count = 0

        # important: add 0 at the begining and in the end
        # won't change if the first and last plot can plant flower
        flowerbed = [0] + flowerbed + [0]

        # scan each plot, check if it can plant flower
        for i in range(1, len(flowerbed)-1):
            if flowerbed[i-1:i+2] == [0,0,0]:
                count += 1
                flowerbed[i] = 1
            if count >= n:
                return True    

        return False