Can Place Flowers

Can Place Flowers is a friendly greedy question. The rule is simple. No two flowers can sit next to each other. The interviewer wants to see if you can make the right local choice at each spot and handle the edges of the array cleanly. Those edges are where most people slip.

🎯 The Problem

You get a flowerbed and a number n. Decide if you can plant n more flowers with no two touching.

• Each box is a plot. A 0 is empty. A 1 already has a flower.
• You must plant n more flowers.
• No two flowers may sit in plots that touch.
• Return true if all n fit. Otherwise false.
• A greedy choice grabs a spot the moment it is safe, without looking far ahead.

Let us say the flowerbed is [1, 0, 0, 0, 1] and n is 1. The middle plot at index 2 is empty. Its neighbors at index 1 and 3 are also empty. So you can plant one flower there. The answer is true.

Input:  flowerbed = [1, 0, 0, 0, 1], n = 1
Output: true

Explanation: plant at index 2, since index 1 and index 3 are both empty

If n were 2 for the same bed, the answer would be false. There is just not enough room without two flowers touching.

Here is a picture of the example bed. The middle empty plot has empty neighbors, so it is plantable.

🐢 Approach 1: Plant Then Re-Scan (Brute Force)

The idea in one line: plant one flower, scan the whole bed again, repeat.

The idea:

• Find one safe empty plot.
• Plant there and lower n by one.
• Start the scan over from the beginning.

How it works:

• Scan the array for a plot that is empty with empty neighbors.
• Plant a flower there.
• Restart the scan for the next flower.

Why it is weak:

• Every flower you plant makes you scan the bed again.
• In the worst case you scan many times.
• That is O(n²) time. A long bed gets slow.

Here is the brute-force code for that idea:

def can_place_flowers(flowerbed, n):
    bed = flowerbed[:]

    def is_valid(index):
        left_empty = index == 0 or bed[index - 1] == 0
        right_empty = index == len(bed) - 1 or bed[index + 1] == 0
        return bed[index] == 0 and left_empty and right_empty

    planted = 0
    for i in range(len(bed)):
        if is_valid(i):
            bed[i] = 1
            planted += 1
            if planted == n:
                return True

    return planted >= n


print(can_place_flowers([1, 0, 0, 0, 1], 1))

⚡ Approach 2: One Greedy Pass (Best)

The idea in one line: walk the bed once and plant at the first safe plot you reach.

The idea:

• Walk the bed left to right one time.
• Plant the moment a plot is safe.
• Never go back.

How it works:

• For each plot, check the plot itself is empty.
• Check the left neighbor is empty or off the edge.
• Check the right neighbor is empty or off the edge.
• Off the edge means before index zero or after the last index, which counts as empty.
• When all three hold, set the plot to 1 and lower n.
• At the end, return true if n dropped to zero or below.

Why it is fast:

• One forward pass touches each plot once. That is O(n).
• It changes the bed in place, so no extra array. That is O(1).
• Taking the earliest legal plot never costs a later one, so greedy is safe here.

This picture shows the greedy pass on [1, 0, 0, 0, 1] with n = 1. Follow the decision at each plot.

Steps to Solve

1. Walk the flowerbed from the first plot to the last.
2. For the current plot, check that it is empty.
3. Check that the left neighbor is empty or off the edge.
4. Check that the right neighbor is empty or off the edge.
5. If all three hold, set the plot to 1 and lower n by one.
6. After the loop, return true if n is zero or less, otherwise false.

#include <stdio.h>

int canPlaceFlowers(int bed[], int size, int n) {
    for (int i = 0; i < size; i++) {
        int empty = (bed[i] == 0);
        int leftFree = (i == 0) || (bed[i - 1] == 0);        // edge counts empty
        int rightFree = (i == size - 1) || (bed[i + 1] == 0); // edge counts empty
        if (empty && leftFree && rightFree) {
            bed[i] = 1;   // plant here
            n--;
        }
    }
    return n <= 0;  // true if we planted enough
}

int main(void) {
    int bed[] = {1, 0, 0, 0, 1};
    int n = 1;
    printf("%s\n", canPlaceFlowers(bed, 5, n) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
using namespace std;

bool canPlaceFlowers(vector<int> bed, int n) {
    int size = bed.size();
    for (int i = 0; i < size; i++) {
        bool empty = (bed[i] == 0);
        bool leftFree = (i == 0) || (bed[i - 1] == 0);
        bool rightFree = (i == size - 1) || (bed[i + 1] == 0);
        if (empty && leftFree && rightFree) {
            bed[i] = 1;   // plant here
            n--;
        }
    }
    return n <= 0;  // true if we planted enough
}

int main() {
    vector<int> bed = {1, 0, 0, 0, 1};
    int n = 1;
    cout << (canPlaceFlowers(bed, n) ? "true" : "false") << endl;
    return 0;
}

true

public class CanPlaceFlowers {
    public static boolean canPlaceFlowers(int[] bed, int n) {
        int size = bed.length;
        for (int i = 0; i < size; i++) {
            boolean empty = bed[i] == 0;
            boolean leftFree = (i == 0) || (bed[i - 1] == 0);
            boolean rightFree = (i == size - 1) || (bed[i + 1] == 0);
            if (empty && leftFree && rightFree) {
                bed[i] = 1;   // plant here
                n--;
            }
        }
        return n <= 0;  // true if we planted enough
    }

    public static void main(String[] args) {
        int[] bed = { 1, 0, 0, 0, 1 };
        int n = 1;
        System.out.println(canPlaceFlowers(bed, n));
    }
}

true

def can_place_flowers(bed, n):
    size = len(bed)
    for i in range(size):
        empty = bed[i] == 0
        left_free = i == 0 or bed[i - 1] == 0          # edge counts as empty
        right_free = i == size - 1 or bed[i + 1] == 0  # edge counts as empty
        if empty and left_free and right_free:
            bed[i] = 1        # plant here
            n -= 1
    return n <= 0             # true if we planted enough


bed = [1, 0, 0, 0, 1]
n = 1
print(can_place_flowers(bed, n))

True

function canPlaceFlowers(bed, n) {
  const size = bed.length;
  for (let i = 0; i < size; i++) {
    const empty = bed[i] === 0;
    const leftFree = i === 0 || bed[i - 1] === 0;        // edge counts empty
    const rightFree = i === size - 1 || bed[i + 1] === 0; // edge counts empty
    if (empty && leftFree && rightFree) {
      bed[i] = 1;   // plant here
      n--;
    }
  }
  return n <= 0;  // true if we planted enough
}

const bed = [1, 0, 0, 0, 1];
const n = 1;
console.log(canPlaceFlowers(bed, n));

true

Let us walk through the Python version line by line. Code first, then the why.

def can_place_flowers(bed, n):
    size = len(bed)
    for i in range(size):
        empty = bed[i] == 0
        left_free = i == 0 or bed[i - 1] == 0
        right_free = i == size - 1 or bed[i + 1] == 0
        if empty and left_free and right_free:
            bed[i] = 1
            n -= 1
    return n <= 0

for i in range(size): walks every plot once, left to right. We never go back. That single forward pass is what makes the greedy method fast.

empty = bed[i] == 0 checks that the current plot has no flower. We can only plant on an empty plot. So this must be true before we even look at the neighbors.

left_free = i == 0 or bed[i - 1] == 0 handles the left side and the left edge in one line. If i is zero, there is no left neighbor, so we treat it as empty. Otherwise the actual left plot must be empty. This i == 0 check is what stops the code from reading before the start of the array.

right_free = i == size - 1 or bed[i + 1] == 0 does the same for the right side. If i is the last index, there is no right neighbor, so it counts as empty. This guard stops the code from reading past the end of the array.

if empty and left_free and right_free: plants only when all three are safe. The plot is empty and both sides are clear. That is the exact rule of the problem.

bed[i] = 1 plants the flower. We change the bed itself, so the next step sees this new flower as the left neighbor. That is why we do not plant two in a row.

n -= 1 lowers how many we still need to plant.

return n <= 0 gives the final answer. If we planted at least as many as asked, n dropped to zero or below, so the answer is true.

⏱️ Time and Space Complexity

The brute force re-scans the bed for every flower, so its time grows as O(n²). The greedy pass walks the bed just once and makes a safe local choice at each plot. So it is O(n) time. It changes the bed in place, so it uses O(1) extra space.

🧩 Key Takeaways

• ✅ A 0 is an empty plot and a 1 is a plot that already has a flower.
• ✅ You can plant on an empty plot only when both neighbors are empty.
• ✅ Treat positions off the edge of the bed as empty.
• ✅ The greedy choice of planting at the earliest safe plot is always correct.
• ✅ One pass and in-place changes give O(n) time and O(1) extra space.

🚀 What’s Next?

• Plus One
• Subarray Sum Equals K