Can Place Flowers

Greedy

15 min

Problem Statement

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 0s and 1s, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Example

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1

flowerbed: [1, 0, 0, 0, 1], n: 1

Output: true

Solution

The greedy approach is to iterate through the flowerbed and place a flower whenever we find an empty plot that has empty plots on both sides (or is at an edge).

Algorithm Steps

Iterate through the flowerbed array.
For each plot, check if it's empty.
If it is, check if the previous and next plots are also empty (or if it's an edge case).
If a flower can be planted, place it (by changing the value to 1) and decrement `n`.
If `n` becomes 0, we can stop and return true.

Can Place Flowers

Greedy Approach

Input: flowerbed = [1, 0, 0, 0, 1], n = 1

Output: false

Progress1 / 1

Ready to start the visualization

Flowerbed

Flowers to Plant (n)

Can Place Flowers Solution


class Solution:
    def canPlaceFlowers(self, flowerbed: list[int], n: int) -> bool:
        f = [0] + flowerbed + [0]
        for i in range(1, len(f) - 1):
            if f[i-1] == 0 and f[i] == 0 and f[i+1] == 0:
                f[i] = 1
                n -= 1
        return n <= 0