Can Place Flowers

easy array greedy

Problem

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

Inputbed = [1, 0, 0, 0, 1], n = 1

Outputtrue

Plant in position 2: result becomes [1, 0, 1, 0, 1].

bed (comma-separated 0/1)

def can_place_flowers(bed, n):
    i = 0
    while i < len(bed) and n > 0:
        if bed[i] == 0 \
                and (i == 0 or bed[i - 1] == 0) \
                and (i == len(bed) - 1 or bed[i + 1] == 0):
            bed[i] = 1; n -= 1
        i += 1
    return n == 0

function canPlaceFlowers(bed, n) {
  for (let i = 0; i < bed.length && n > 0; i++) {
    if (bed[i] === 0
        && (i === 0 || bed[i - 1] === 0)
        && (i === bed.length - 1 || bed[i + 1] === 0)) {
      bed[i] = 1; n--;
    }
  }
  return n === 0;
}

class Solution {
    public boolean canPlaceFlowers(int[] bed, int n) {
        for (int i = 0; i < bed.length && n > 0; i++) {
            if (bed[i] == 0
                    && (i == 0 || bed[i - 1] == 0)
                    && (i == bed.length - 1 || bed[i + 1] == 0)) {
                bed[i] = 1; n--;
            }
        }
        return n == 0;
    }
}

bool canPlaceFlowers(vector<int>& bed, int n) {
    for (int i = 0; i < (int)bed.size() && n > 0; i++) {
        if (bed[i] == 0
                && (i == 0 || bed[i - 1] == 0)
                && (i == (int)bed.size() - 1 || bed[i + 1] == 0)) {
            bed[i] = 1; n--;
        }
    }
    return n == 0;
}

Explanation

The greedy rule is to plant a flower in the very first spot that is legal, scanning left to right. Planting as early as possible never blocks a future planting you could otherwise have made, so it is always safe.

A plot i is plantable when it is empty (bed[i] == 0) and both neighbors are empty too. The edge cases are handled by treating off-the-array sides as empty: i == 0 means no left neighbor, and i == len(bed) - 1 means no right neighbor.

When we find such a spot, we set bed[i] = 1 and decrement n. Marking it planted automatically prevents the next cell from also being chosen, since it now sees a filled left neighbor. At the end we just check whether n reached 0.

Example: bed = [1, 0, 0, 0, 1], n = 1. Index 1 has a filled left neighbor, but index 2 is empty with empty neighbors, so we plant there. That uses up the single flower, giving true.

Time: O(L) Space: O(1)