Can Place Flowers

TARGET DECK: Leetcode FILE TAGS: Easy

---

Intuition

• What tripped me up with this problem was the logic with checking if a flower was valid to be placed.
• To achieve this:
  • Mark flowers adjacent to an existing flower position as x.
  • Then, if you encounter a valid position (that is not an x or a 1):
    • Place a 1 in that position, and mark the adjacent values as x as was done before.
• At the end, check if you have placed enough hours to say I placed n flowers at the very least. It could be more.

Complexity

Runtime

$O(N)$, where N is the length of the array, and you are doing a sweep of the elements on the array.

Space

• $O(1)$ since we are clobbering the original array.
• Otherwise, would have to create a new array copy of the old one.

Code

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        for i in range(len(flowerbed)):
            if flowerbed[i] == 0:
                is_valid = True
                for adj in [i - 1, i + 1]:
                    if 0 <= adj < len(flowerbed) and flowerbed[adj] == 1:
                        is_valid = False
                        break
 
                if is_valid:
                    flowerbed[i] = 1
                    n -= 1
 
            if flowerbed[i] == 1:
                for adj in [i - 1, i + 1]:
                    if 0 <= adj < len(flowerbed) and flowerbed[adj] != 1:
                        flowerbed[adj] = -1
 
        return n <= 0

Notes

Cards

START Basic Front: Can Place Flowers Back: Mark adjacent elements as x to avoid placing flowers there, while marking valid flower positions as 1.

END

---

References

• Can Place Flowers