605 Can Place Flowers

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

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.

The Idea: To simplify things later, consider the edges of the array. If there are at least two zeros, this is it always optimal to place a flower on the absolution edge of array because this edge is not constrained by adjacent flowers in any way. Now having this done, we can simply iterate through the array, and count the consecutive zeros. We notice the following pattern with given n consecutive 0s. This is simply math.floor((consec_count - 1) / 2.

n | opt
-------
1 | 0
2 | 0
3 | 1
4 | 1
5 | 2
6 | 2
7 | 3
. | .
. | .
. | .

Complexity: O(N) time and O(1) space

class Solution:
    def canPlaceFlowers(self, flowerbed, n):
        """
        :type flowerbed: List[int]
        :type n: int
        :rtype: bool
        """
        if len(flowerbed) is 1 and \
            flowerbed[0] is 0:
            return True
        if len(flowerbed) >= 2 and \
           flowerbed[0] is 0 and \
           flowerbed[1] is 0:
            flowerbed[0] = 1
            n -= 1

        if len(flowerbed) >= 3 and \
           flowerbed[-1] is 0 and \
           flowerbed[-2] is 0:
            flowerbed[-1] = 1
            n -= 1

        consec_count = 1
        for i in range(1, len(flowerbed)):
            if flowerbed[i-1] is flowerbed[i]:
                consec_count += 1
            else:
                n -= math.floor((consec_count - 1) / 2)
                consec_count = 1

        return n <= 0

Testing

obj = Solution()
print(obj.canPlaceFlowers([1, 0, 0, 0, 1], 1))  # T
print(obj.canPlaceFlowers([1, 0, 0, 0, 1], 2))  # F
print(obj.canPlaceFlowers([1, 0, 0, 1, 0, 1], 1))  # F
print(obj.canPlaceFlowers([0, 0, 1, 0, 1, 1], 1))  # T
print(obj.canPlaceFlowers([0, 0, 0, 0, 0, 0], 3))  # T
print(obj.canPlaceFlowers([0, 0, 0, 0, 0, 0], 4))  # F