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:
The description was taken from https://leetcode.com/problems/can-place-flowers/.
#O(N) Time, O(1) Spaceclass Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool: flowerbed.insert(0,0) flowerbed.append(0) count = 0 for plot in flowerbed: if plot == 0: count += 1 else: count = 0 if count == 3: n -= 1 count = 1 if n == 0: return True return FalseThis question can be solved using a consecutive element counter, a sort of precursor to the sliding window algorithm.
A flower can only be planted if there is an empty plot on both sides of the plot we'd like to plant a flower in. Each time we come across an empty plot, we will increment a counter. Each time we come across an occupied plot, we will reset the counter.
Whenever the counter is a three, we will plant a flower by decrementing n. If n is zero by the time we reach the end of the array, we were able to plant all of the flowers.
We will start by initializing our count to zero, then adding a zero to both the beginning and the end of the array.
A vacant flowerbed must be three zeros if it is in the middle of the array. If it's on one of the edges, it only has to be two. This handles that scenario.
flowerbed.insert(0,0) flowerbed.append(0) count = 0
Next, we will traverse each plot element in the flowerbed array.
for plot in flowerbed:
If we come across a zero, we will increment the counter.
If we come across anything other than a zero then that means we can't place flowers there and we will reset the count.
if plot == 0: count += 1 else: count = 0
Each time the counter is a three, we have three consecutive empty plots so we will plant a flower that we take from n.
if count == 3: n -= 1
We will reset our count to one. We don't set it back to zero if we just planted because we will only require two more empty plots after the flower we just planted if we want to avoid neighboring another flower with this flower.
count = 1
If n is zero, we have run out of flowers to plant so we will return true because that would mean we can plant all the flowers.
if n == 0: return True
If true was never returned from the loop then that means we still have flowers we couldn't plant so we will return false.
return False