1. Can Place Flowers (LeetCode)
Model answer
The task
Given a row of plots where 1 marks an occupied plot and 0 an empty one, decide whether at least n flowers can be added without placing flowers in neighboring plots.
Key idea
Scan from left to right, planting in an empty plot whenever both neighboring plots are empty or outside the row. Greedily planting at the earliest available plot cannot reduce the number of later planting opportunities.
Approach
- Return
Trueimmediately ifnis zero. - Visit each plot from left to right.
- For an empty plot, check its left and right neighbors, treating the row boundaries as empty.
- If both are empty, plant there and decrement
n. - Return
Trueoncenreaches zero; otherwise return whether it reached zero by the end.
from typing import List
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True
for i in range(len(flowerbed)):
if flowerbed[i] == 0:
left_empty = i == 0 or flowerbed[i - 1] == 0
right_empty = (
i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
)
if left_empty and right_empty:
flowerbed[i] = 1
n -= 1
if n == 0:
return True
return False
Complexity:
- Time: O(m), where
mis the number of plots; each plot is checked at most once. - Space: O(1), using only a fixed amount of extra space.
Common follow-ups
- What if the input must not be modified? Track the previous plot’s occupancy instead of planting in the array.
- How would you return the planting positions? Record each plot index when the greedy rule permits planting.
- What if plots wrap around in a circle? Handle the first and last plots as neighbors, with special care for rows of length one or two.