Can Place Flowers

A long garden bed is split into plots in a single row. You're given flowerbed, an array where 1 means a plot already has a flower and 0 means it's empty. The existing flowers never touch each other.

Flowers can't grow in adjacent plots. Given an integer n, return true if you can plant n more flowers in empty plots without any two flowers ending up next to each other, and false otherwise.

The two ends of the bed have no neighbor on the outside, so an empty end plot only needs its one inside neighbor to be empty.

Walk the bed from left to right. Whenever a plot is empty and both of its neighbors are empty (treating the outside of the bed as empty), plant there right away.

Why is planting early never a mistake? A flower at plot i only blocks plots i - 1 and i + 1. Plot i - 1 was already passed over, and any plan that skips i to plant at i + 1 can shift that flower left to i without hurting anything to its right. So the greedy count is the maximum possible, and you can stop as soon as it reaches n.

def can_place_flowers(flowerbed: list[int], n: int) -> bool:
    size = len(flowerbed)
    i = 0
    while i < size and n > 0:
        if flowerbed[i] == 1:
            i += 2  # the next plot is blocked
            continue
        left_empty = i == 0 or flowerbed[i - 1] == 0
        right_empty = i == size - 1 or flowerbed[i + 1] == 0
        if left_empty and right_empty:
            n -= 1
            i += 2
        else:
            i += 1
    return n <= 0

function canPlaceFlowers(flowerbed, n) {
  const size = flowerbed.length;
  let i = 0;
  while (i < size && n > 0) {
    if (flowerbed[i] === 1) {
      i += 2; // the next plot is blocked
      continue;
    }
    const leftEmpty = i === 0 || flowerbed[i - 1] === 0;
    const rightEmpty = i === size - 1 || flowerbed[i + 1] === 0;
    if (leftEmpty && rightEmpty) {
      n--;
      i += 2;
    } else {
      i++;
    }
  }
  return n <= 0;
}

Say why greedy is safe in one sentence: "planting at the leftmost legal plot never blocks more than any other choice." Interviewers often ask for that justification on an easy problem to see whether you prove greedy choices or just hope.

Ask whether you're allowed to modify the input. If not, show the skip-ahead version, which reads the array without changing it. Mention the early exit once n hits 0.