LeetCode 605. Can Place Flowers

September 13, 2020

It looks like we can solve this greedily in $O(n)$ time.

Our algorithm looks like:

For each element, if the previous and following elements are both 0, change it to a 1 and increment a counter.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0,1], 1), True)
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0,1], 2), False)

    def test_empty(self):
        self.assertEqual(self.s.canPlaceFlowers([], 0), True)
        self.assertEqual(self.s.canPlaceFlowers([], 2), False)

    def test_ends(self):
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0], 1), True)
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0], 2), False)

    def test_even_space(self):
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,1], 0), True)
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,1], 1), False)
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0,0,1], 1), True)
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0,0,1], 2), False)

    def test_segments(self):
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0,1,0,0,0,1], 2), True)
        self.assertEqual(self.s.canPlaceFlowers([1,0,0,0,1,0,0,0,1], 3), False)

class Solution:

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

if __name__ == "__main__":
    unittest.main()