LeetCode 605

July 12, 2024

605. Can Place Flowers

Problem

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.

Solution

Simple Checks

First, we think of what parameters we need to place a flower. We must know if the left and right are empty, then we can place one. This seems simple enough, but we must also keep edge cases in mind.

Edge Cases

We find our solution failing at two specific edge cases. Think of when our checks will be out of bounds. When looking at our array visual we can see that at our array bounds, it fails. We can solve this by putting in additional cases for left and right, where if we are in the first pot, the left is not containing a flower. Also for the other end we can say that the right pot is empty.

[0, 0, 0, 0, 0]
 ^           ^
 # Edge Cases

Code

count = 0
for i in range(len(flowerbed)):
	if flowerbed[i] == 0:
    left = i == 0 or flowerbed[i - 1] == 0
    right = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
    if left and right:
	    flowerbed[i] = 1
	    count += 1
    return count >= n

Bug I Encountered

Something that had caused issues for me is that we need to make sure we are placing a flower every time we find an open pot. If we do not, the issue of counting a spot when a flower should have been placed.

# Wrong
[0, 0, 0, 0, 1]
 ^	^  ^  
# Will place if not changing pot value, count = 3
 
# Correct
[0, 0, 0, 0, 1]
 ^ 
[1, 0, 0, 0, 1]
       ^ 
[1, 0, 1, 0, 1] 

# count = 2