Can Place Flowers — Algorithmics

A row of plots, some already planted. No two flowers may be adjacent. Can you plant n more?

canPlaceFlowers([]int{1, 0, 0, 0, 1}, 1)   // true
canPlaceFlowers([]int{1, 0, 0, 0, 1}, 2)   // false

Plant at the first opportunity

Walk left to right. A plot is plantable when it is empty and both neighbours are empty — with the ends counting as empty, since there is nothing beyond them.

Plot 1 / 5

plant 1 · 1 still to place

❀···❀

left clear: true right clear: true

Already occupied. Nothing to decide.

func canPlaceFlowers(flowerbed []int, n int) bool {
    if n == 0 {
        return true
    }

    for i, v := range flowerbed {
        left := i == 0 || flowerbed[i-1] == 0
        right := i == len(flowerbed)-1 || flowerbed[i+1] == 0

        if left && right && v == 0 {
            n--
            flowerbed[i] = 1
        }

        if n == 0 {
            return true
        }
    }

    return false
}

$O(n)$ time, one pass.

The boundary conditions are the problem

i == 0 and i == len(flowerbed)-1 are doing real work. An end plot has only one neighbour, and treating the missing one as occupied would reject [0] with n = 1, which is plantable.

The alternative spelling — pad the bed with a zero at each end and drop the special cases — is worth knowing:

padded := append([]int{0}, append(flowerbed, 0)...)

Cleaner logic, an allocation, and one more thing to get right in the index arithmetic. For a single check either is fine; for anything with more neighbour rules, padding usually wins.

It rewrites the caller’s flowerbed

A predicate that mutates its argument

bed := []int{1, 0, 0, 0, 1}
canPlaceFlowers(bed, 1)
fmt.Println(bed)          // [1 0 1 0 1] — a flower was planted

The function is named like a question and behaves like a command. Nothing in canPlaceFlowers(bed, n) bool suggests bed comes back different, and a caller who checks twice gets two different answers.

The mutation is not needed for correctness — it exists to stop the next plot being considered plantable. A counter does the same job without touching the input:

func canPlaceFlowers(flowerbed []int, n int) bool {
    gap := 1                       // a virtual empty plot before the start

    for _, plot := range flowerbed {
        if plot == 1 {
            gap = 0
            continue
        }
        gap++
        if gap == 3 {              // empty, empty, empty → plant in the middle
            n--
            gap = 1                // the planted flower restarts the run
        }
    }

    return n <= gap/2+0            // …plus whatever the trailing run allows
}

The simplest fix, if you want to keep the original shape, is one line at the top: flowerbed = slices.Clone(flowerbed). Callers stop being surprised, at the cost of an allocation.

Counting instead of simulating

There is a closed form. A run of k consecutive empty plots between two flowers holds $\lfloor (k-1)/2 \rfloor$ new ones; a run at either end holds $\lfloor k/2 \rfloor$ , because it only has a neighbour on one side.

Summing those and comparing to n is the same $O(n)$ and it never writes to the input. It is also easier to get wrong — three cases instead of one — which is why the simulation is the version to reach for first and this is the version to reach for when the input is not yours to modify.