Things

Can Place Flowers (LC 605)

2 min read

Pattern: Greedy → plant as early as possible
Difficulty: Easy
Time: O(n) | Space: O(1) extra

Problem

A flowerbed is an array of 0 (empty) and 1 (planted). Flowers can’t be planted next to each other.
Can you plant n more flowers without breaking that rule?

flowerbed = [1,0,0,0,1], n = 1 → true (plant in the middle)
flowerbed = [1,0,0,0,1], n = 2 → false

Core idea

Walk left to right. If a spot and both its neighbours are empty, plant there right away.

  1. Skip spots that are already planted.
  2. A spot is plantable when left is empty and right is empty.
    • Off the edge counts as empty (index -1 and index length).
  3. Plant it (flowerbed[i] = 1), decrease n, and skip the next spot.
  4. Stop early once n hits 0.

Why greedy works: planting at the earliest possible spot never blocks more spots than planting later would. Waiting can’t help.

Code (TypeScript)

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
  for (let i = 0; i < flowerbed.length && n > 0; i++) {
    if (flowerbed[i] === 1) continue;
 
    const leftEmpty = i === 0 || flowerbed[i - 1] === 0;
    const rightEmpty = i === flowerbed.length - 1 || flowerbed[i + 1] === 0;
 
    if (leftEmpty && rightEmpty) {
      flowerbed[i] = 1; // plant it so the next check sees it
      n--;
      i++; // the next spot is now blocked, skip it
    }
  }
  return n === 0;
}

Gotchas

  • Edges: the first and last spots only have one neighbour. Treat “off the edge” as empty.
  • Mark the plant. If you don’t set flowerbed[i] = 1, [0,0,0] would plant at 0 and 1.
  • n = 0 is always true, even for [1].
  • This changes the input array. If that’s not allowed, track “planted previous spot” in a variable instead.
  • Test: [0] with n=1, [0,0,1,0,0] with n=2, [1,0,0,0,0,1] with n=2 (false).

Pattern to remember

“Take it as soon as it’s allowed” is greedy. It works when taking now never makes later choices worse.

Graph View

Backlinks