Can Place Flowers

GREEDY · EASY

The problem

You have a long flowerbed, represented as an array of 0s and 1s — 0 means an empty plot, 1 means a plot that already has a flower. Flowers can never sit in two adjacent plots. Given the flowerbed and a number n, decide whether n new flowers can be planted somewhere in it without ever putting two flowers next to each other.

Solution 1: Brute force — plant, then rescan the WHOLE array

The cautious way to check “is this placement legal?” is to actually place it and then re-verify the entire flowerbed from scratch, checking every adjacent pair for a conflict. For every empty plot, try planting there, rescan everything, and keep the flower only if the full rescan comes back clean. It’s correct — but each rescan is O(len) work, and there can be up to O(len) candidate plots, so the whole thing costs O(len²).

tentative plant, being rescanned rejected — rescan found a conflict flower committed occupied, skipped flowerbed=[0, 0, 1, 0, 0, 0, 1], n=2

Press Play or Step to begin.

Step 0 / 14

function isValidFull(bed) {
  for (let i = 0; i < bed.length; i++) {
    if (bed[i] === 1 && i + 1 < bed.length && bed[i + 1] === 1) return false;
  }
  return true;
}

function canPlaceBruteForce(flowerbed, n) {
  const bed = flowerbed.slice();
  let count = 0;
  for (let i = 0; i < bed.length; i++) {
    if (bed[i] === 0) {
      const trial = bed.slice();
      trial[i] = 1;
      if (isValidFull(trial)) {
        bed[i] = 1;
        count++;
      }
    }
  }
  return count >= n;
}

Line by line:

isValidFull walks every plot and flags a conflict if two adjacent plots are both 1 — a full O(len) check, run from scratch every time it’s called.
For every empty plot, trial is a fresh copy of the working bed with a flower dropped in at i — the original bed is never mutated until the trial is confirmed safe.
isValidFull(trial) re-checks the ENTIRE array, not just the two neighbors of i — that’s the wasted work, since only those two neighbors could possibly have changed.
Only on success is the real bed updated and count incremented — a rejected trial is simply thrown away.

Complexity: O(len²) time, O(len) space — per-plot trial + full-array rescan.

Solution 2: Optimal — one greedy left-to-right pass

You don’t need to rescan the whole array — a plot’s legality only ever depends on its own two immediate neighbors, and once you’ve moved past a plot, nothing you do later can make it illegal again. So walk once, left to right: if a plot is empty and both neighbors are empty (or off the edge of the array), plant immediately and never look back. That’s the greedy insight — the locally best choice at each plot is also globally optimal, because planting as early as possible only ever helps future plots, never hurts them.

plot being examined has a flower (original or newly planted) flowerbed=[0, 0, 1, 0, 0, 0, 1], n=2

Press Play or Step to begin.

Step 0 / 11

function canPlaceOptimal(flowerbed, n) {
  const bed = flowerbed.slice();
  let count = 0;
  for (let i = 0; i < bed.length; i++) {
    const leftEmpty = i === 0 || bed[i - 1] === 0;
    const rightEmpty = i === bed.length - 1 || bed[i + 1] === 0;
    if (bed[i] === 0 && leftEmpty && rightEmpty) {
      bed[i] = 1;
      count++;
    }
  }
  return count >= n;
}

Line by line:

bed = flowerbed.slice() works on a private copy purely so this demo never mutates the caller’s array — the algorithm itself needs no extra array at all beyond a running counter, so its own extra space is O(1).
leftEmpty / rightEmpty treat the edges of the array as empty — i === 0 short-circuits before bed[i - 1] is ever read, same for i === bed.length - 1 before bed[i + 1].
The moment a plot is planted, bed[i] = 1 updates the SAME array the next iteration’s leftEmpty check reads — that’s what makes two flowers ending up adjacent structurally impossible, with no extra bookkeeping.
Each plot is visited exactly once and every check is O(1) — that’s the whole O(len).

Complexity: O(len) time, O(1) space — single greedy left-to-right pass.

Complexity comparison

Solution	Time	Space
Brute force (trial + full rescan)	O(len²)	O(len)
Optimal (greedy one pass)	O(len)	O(1)

Interview corner

Why is it safe to plant greedily as early as possible, without ever reconsidering that choice later?

Planting a flower can only ever block its own two immediate neighbors — it never affects any plot further away.
Planting as EARLY as possible (the first legal moment) leaves the maximum possible room for future plots, compared to waiting.
So the locally best choice at each plot — plant now if you legally can — never costs you a better global outcome later. That’s exactly what makes this greedy, not just “an approximation.”

Why does the brute-force version need a full array rescan instead of just checking the two neighbors, like the optimal version does?

It doesn’t NEED to — that’s exactly the point of this problem. The rescan is strictly wasted work.
Structurally, only plot i-1 and plot i+1 could possibly conflict with a flower newly planted at i — nothing else in the array changed.
Checking the whole array is a “safe but naive” habit — it’s correct, but it pays O(len) per placement when O(1) would do.

How would you handle a circular flowerbed, where the first and last plots are also considered adjacent?

Change the edge cases: instead of treating i === 0 and i === bed.length - 1 as “automatically empty,” wrap around and read bed[bed.length - 1] and bed[0] respectively.
The rest of the single-pass logic is unchanged — still O(len), still one greedy pass.
Worth calling out explicitly in an interview: this is exactly the kind of boundary assumption that’s easy to silently get wrong if you don’t ask about it first.

Trick question — does this throw an error?

const bed = [1, 0, 0];
console.log(bed[-1]);
console.log(bed[10]);
console.log(bed[-1] === 0);

Answer: no error either time. Both log undefined.
JavaScript array indexing never throws on an out-of-bounds index (positive or negative) — it just returns undefined, silently.
So bed[-1] === 0 is false — undefined is not loosely OR strictly equal to 0.

⚠️ Trap: This is exactly why the optimal solution’s boundary check is written as i === 0 || bed[i - 1] === 0 and never as a bare bed[i - 1] === 0. Relying on bed[-1] === 0 being “empty” would silently be false at the left edge — the explicit i === 0 check comes first specifically to short-circuit before that out-of-bounds read ever happens.

Quiz

1. Why does the optimal solution only need to check a plot’s two immediate neighbors, instead of rescanning the whole array like brute force does?

A newly planted flower can only possibly conflict with its own two immediate neighbors — nothing farther away changed
It only works because the example inputs are small
It’s an approximation that trades some correctness for speed

2. What is the core greedy insight that makes “plant as early as legally possible” the globally optimal strategy, not just a fast approximation?

Planting at the earliest legal plot never leaves LESS room for future plots than waiting would — so it’s never a worse choice
Greedy choices are always optimal for every problem, by definition
It happens to work only on the specific test cases shown here

3. In leftEmpty = i === 0 || bed[i - 1] === 0, what is the i === 0 check actually protecting against?

It short-circuits before an out-of-bounds read like bed[-1], which would silently be undefined rather than 0
It’s a performance optimization with no correctness impact
It’s dead code — bed[-1] would throw anyway so it’s never reached

4. After the optimal solution plants a flower at index i (bed[i] = 1), how does the next iteration “know” that plot is now occupied?

The next iteration’s leftEmpty check reads bed[i - 1] from the SAME array that was just mutated, so the update is automatically visible
A separate “planted” set is checked alongside bed on every iteration
It doesn’t — that’s a latent bug in the algorithm

5. What’s the time complexity difference between the two solutions, and why?

Brute force is O(len²) from rescanning the whole array per candidate plot; optimal is O(len) from checking only 2 neighbors per plot
They’re the same — O(len) for both
Brute force is O(len); optimal is O(len²)