algoadvance

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.

Given an integer 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.

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

Clarifying Questions

  1. What are the constraints on the size of the flowerbed array?
    • The length of the flowerbed will be in the range [1, 2 * 10^4].
  2. Will the flowerbed array always be valid (containing only 0s and 1s)?
    • Yes.
  3. Can we solve this problem in-place, or is additional space allowed?
    • Preferably in-place, but using extra space is allowed if necessary.

Strategy

To solve this problem, we need to iterate through the flowerbed array and try to plant flowers in the available spots. To determine if a flower can be planted at a specific index i, we need to check three conditions:

  1. flowerbed[i] == 0: The current spot is empty.
  2. i == 0 or flowerbed[i-1] == 0: Either we are at the beginning of the array or the previous spot is empty.
  3. i == len(flowerbed)-1 or flowerbed[i+1] == 0: Either we are at the end of the array or the next spot is empty.

If all three conditions above are fulfilled, we can plant a flower at index i and increment our counter for planted flowers. If at any point the number of planted flowers meets or exceeds n, we return True. If we finish iterating through the array and haven’t planted enough flowers, we return False.

Code

def canPlaceFlowers(flowerbed, n):
    count = 0  # Counter for planted flowers
    i = 0
    
    while i < len(flowerbed):
        if flowerbed[i] == 0:
            # Check if left and right positions are empty or at boundary
            empty_left = (i == 0) or (flowerbed[i-1] == 0)
            empty_right = (i == len(flowerbed) - 1) or (flowerbed[i+1] == 0)
            
            if empty_left and empty_right:
                flowerbed[i] = 1  # Plant a flower
                count += 1
                if count >= n:
                    return True
                # Skip the next spot as we can't plant adjacent
                i += 2
                continue
        
        i += 1
    
    return count >= n

Time Complexity

The time complexity of this solution is O(m) where m is the length of the flowerbed. This is because we iterate through the array once, making constant time checks and updates.

The space complexity is O(1) since we are modifying the input array in-place and only using a few additional variables.

Try our interview co-pilot at AlgoAdvance.com