Taro Logo

Can Place Flowers

Easy
Meta logo
Meta
Topics:
ArraysGreedy Algorithms

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 true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

For example:

  1. If the input is flowerbed = [1,0,0,0,1], n = 1, the output should be true.
  2. If the input is flowerbed = [1,0,0,0,1], n = 2, the output should be false.

What is the most efficient way to determine if n new flowers can be planted?

Solution


Naive Solution

A brute force approach would be to iterate through the flowerbed array and check at each plot if a flower can be planted. For each plot, we need to check if the adjacent plots are empty. If a flower can be planted, we plant it (update the array) and decrement n. Finally, we check if n is zero or negative. If so, we return true; otherwise, we return false.

Code

def can_place_flowers_naive(flowerbed, n):
    count = 0
    for i in range(len(flowerbed)):
        if flowerbed[i] == 0:
            #check adjacent slots
            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
                count += 1

    return count >= n

Big O Runtime

  • Time Complexity: O(m), where m is the length of the flowerbed array, because we iterate through the entire array once.

Big O Space Usage

  • Space Complexity: O(1), since we're modifying the input array in place; the extra space used is constant.

Optimal Solution

The optimal solution improves the space complexity. Instead of modifying the array in-place, which might be undesirable, we can check the conditions on the fly without modifying the original array. Additionally, minor improvements can be achieved by reducing the number of checks performed in the loop.

Code

def can_place_flowers_optimal(flowerbed, n):
    count = 0
    m = len(flowerbed)

    for i in range(m):
        if flowerbed[i] == 0:
            left_empty = (i == 0) or (flowerbed[i - 1] == 0)
            right_empty = (i == m - 1) or (flowerbed[i + 1] == 0)

            if left_empty and right_empty:
                count += 1
                flowerbed[i] = 1  # Plant the flower (virtually)
                if count >= n:
                    return True

    return count >= n

Another optimal solution (without modifying input array):

def can_place_flowers(flowerbed, n):
    count = 0
    for i in range(len(flowerbed)):
        if flowerbed[i] == 0:
            prev_empty = (i == 0) or (flowerbed[i - 1] == 0)
            next_empty = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
            if prev_empty and next_empty:
                count += 1
                if count >= n:
                    return True
                flowerbed[i] = 1  # Avoid planting in the next iteration
    return count >= n

Big O Runtime

  • Time Complexity: O(m), where m is the length of the flowerbed array.

Big O Space Usage

  • Space Complexity: O(1), as we are using only a constant amount of extra space.

Edge Cases

  • Empty flowerbed: If the flowerbed is empty, then n must be 0 (or negative), otherwise it's impossible.
  • Single plot flowerbed: If the flowerbed has only one plot, we can plant a flower if the plot is empty and n is 1.
  • Flowerbed with all plots occupied: If all plots are occupied (all elements in flowerbed are 1), it's impossible to plant any flower if n > 0.
  • Flowerbed with alternating empty and occupied plots: In the best-case scenario, the flowerbed may have alternating empty and occupied plots. In this case, we should be able to plant more flowers.