Solution: Can Place Flowers

Statement

Given an integer list flowerbed, each element is either $0$ (indicating an empty plot) or $1$ (indicating a planted plot), and an integer n. Determine if n new flowers can be planted without violating the rule that no two flowers can be planted in adjacent plots. Return TRUE if it’s possible to plant all n flowers. Otherwise, return FALSE.

Constraints:

• $1\leq$ flowerbed.length $\leq10^3$

• $0\leq$ n $\leq$ flowerbed.length

• flowerbed[i] is $0$ or $1$.

• There are no two adjacent flowers in the flowerbed.

Solution

This solution applies a greedy approach to determine if the required number of flowers can be planted in the flowerbed without placing two flowers next to each other. Through the greedy technique, flowers are planted in the flowerbed at the earliest possible empty positions when a spot is not adjacent to any flower. By filling these valid plots, the flower count is increased avoiding future conflicts with potential plantable spots further in the list. This way, chances of planting the flowers without needing to look ahead or reconsider earlier decisions are maximized.

Here’s the step-by-step implementation of the solution:

• Set a counter to $0$, which tracks the number of flowers successfully planted.

• For each position in the flowerbed:

  • Check if the current index is $0$ (indicating an empty plot):

    • Check if the current index’s left and right neighbors of the current index are also $0$ or if the current index is at the boundary of the flowerbed.

    • Left condition: The current index is the first plot (left boundary), or the current index $-~1$ is $0$.

    • Right condition: The current index is the last plot (right boundary), or the current index $+~1$ is $0$.

    • If both left and right conditions are satisfied:

      • Place a flower at the current index position and increment the count by $1$.

    • After planting, if the count equals $n$, return TRUE as the required number of flowers is planted.

  • Otherwise, move on to the next index if the current index is $1$ (indicating a flower).

• If the loop finishes without planting $n$ flowers, return FALSE; otherwise, return TRUE.

Let’s look at the following illustration to get a better understanding of the solution: