Problem Statement
leetcode problem link
Brute Force [Accepted]
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True
prev_flower = 0
for i, flower in enumerate(flowerbed):
prev_flower = flowerbed[i - 1] if i - 1 >= 0 else 0
next_flower = flowerbed[i + 1] if i + 1 < len(flowerbed) else 0
if flower == 0 and prev_flower == 0 and next_flower == 0:
flowerbed[i] = 1
n -= 1
if n == 0:
return True
return False
Editorial
Approach #1 Single Scan [Accepted]
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
count = 0
for i in range(len(flowerbed)):
# Check if the current plot is empty.
if flowerbed[i] == 0:
# Check if the left and right plots are empty.
empty_left_plot = (i == 0) or (flowerbed[i - 1] == 0)
empty_right_lot = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
# If both plots are empty, we can plant a flower here.
if empty_left_plot and empty_right_lot:
flowerbed[i] = 1
count += 1
return count >= n
Approach #2 Optimized [Accepted]
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
count = 0
for i in range(len(flowerbed)):
# Check if the current plot is empty.
if flowerbed[i] == 0:
# Check if the left and right plots are empty.
empty_left_plot = (i == 0) or (flowerbed[i - 1] == 0)
empty_right_lot = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
# If both plots are empty, we can plant a flower here.
if empty_left_plot and empty_right_lot:
flowerbed[i] = 1
count += 1
if count >= n:
return True
return count >= n