Originally from Unit 3 Session 2 (Click for link to problem statements)
Reviewed in Unit 10 Session 1
Understand what the interviewer is asking for by using test cases and questions about the problem.
[0, 0, 1]
, a valid placement would be [1, 0, 1]
.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Loop through the list, checking elements before/after, and adding flowers as we go.
1) Count starts at 0
2) For each index in the flowerbed:
a) If the plot at index is empty:
i) If elements before/after are both empty, add to count
ii) If we've placed enough flowers, return True
3) We weren't able to place enough, so return False
⚠️ Common Mistakes
def can_place_flowers(flowerbed, n):
count = 0 # Count of flowers that can be planted
length = len(flowerbed)
for i in range(length):
# Check if the current plot is empty
if flowerbed[i] == 0:
# Check the previous and next plot, considering the edge cases
prev_empty = i < 0 or flowerbed[i - 1] == 0
next_empty = i >= length or flowerbed[i + 1] == 0
# If both adjacent plots are empty, plant a flower here
if prev_empty and next_empty:
flowerbed[i] = 1 # Mark this plot as planted
count += 1 # Increment the count of flowers that can be planted
# If we've planted enough flowers, return true immediately
if count >= n:
return True
# After checking all plots, if we've planted enough flowers, return true; otherwise, false
return count >= n