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:
flowerbed = [1,0,0,0,1], n = 1
, the output should be true
.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?
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
.
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
flowerbed
array, because we iterate through the entire array once.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.
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
flowerbed
array.flowerbed
is empty, then n
must be 0 (or negative), otherwise it's impossible.flowerbed
has only one plot, we can plant a flower if the plot is empty and n
is 1.flowerbed
are 1), it's impossible to plant any flower if n > 0
.