Back to solutions

Can Place Flowers

EasyArrays

Decide whether n new flowers can be planted in a bed with no two adjacent.

Open problem
Constraints
  • 1 <= m <= 2*10^4
  • 0 <= n <= m
  • Each plot is 0 or 1

Greedy single scan

Time O(m)Space O(1)

Walk the bed left to right. A plot can take a flower when it is empty and both neighbours are empty (or out of bounds). Plant greedily the moment it is legal and count it; planting as early as possible never blocks a better choice. Stop caring once the count reaches n.

Key terms
greedy:
Make the locally best choice (plant as soon as it is allowed) and trust it leads to the global best.
boundary check:
Treating positions before index 0 and after the last index as empty so edge plots are handled.
bool canPlaceFlowers(vector<int>& bed, int n) {
    int count = 0, m = bed.size();
    for (int i = 0; i < m; i++) {
        if (bed[i] == 0 && (i == 0 || bed[i - 1] == 0) &&
            (i == m - 1 || bed[i + 1] == 0)) {
            bed[i] = 1;
            count++;
        }
    }
    return count >= n;
}
Step by step
  1. Set count = 0.
  2. For each plot i, check it is 0 and the left neighbour (or edge) and right neighbour (or edge) are also 0.
  3. If so, set bed[i] = 1 and increment count planting here cannot hurt later plots.
  4. After the scan, return whether count >= n.