Problem Statement in English

You’re given an array flowerbed containing 0’s and 1’s, where 0 means empty and 1 means not empty, and an integer n. Return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Approach

We can use a recursive approach with memoization to solve this problem. We will define a recursive function dp(i, prev) that returns the maximum number of flowers that can be planted starting from index i with the previous plot being prev (True if the previous plot has a flower, False otherwise).

In the recursive function, we have two choices at each index: either we can plant a flower (if the current plot is empty and the previous plot does not have a flower) or we can skip planting a flower. We will take the maximum of these two choices.

Finally, we will compare the maximum number of flowers that can be planted with the existing number of flowers in the flowerbed to determine if we can plant n new flowers.

And we’re done!

Solution in Python


class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        N = len(flowerbed)

        existing = flowerbed.count(1)

        @cache
        def dp(i, prev):
            if i >= N:
                return 0

            take = skip = 0

            if flowerbed[i] and prev:
                return -N

            if not prev and not flowerbed[i]:
                take = 1 + dp(i + 1, True)
            skip = (1 if flowerbed[i] == 1 else 0) + dp(i + 1, flowerbed[i] == 1)
        
            return max(take, skip)

        return dp(0, False) - existing >= n

Complexity

  • Time: $O(N)$
    Since we traverse the array once and memoize the results.

  • Space: $O(N)$
    Since we use memoization which can store up to N results.

Mistakes I Made

I forgot to account for cases when we place a flower and the next plot already has a flower.

And we are done.