Can Place Flowers

Can Place Flowers

What is this problem about?

The Can Place Flowers interview question asks if you can plant n new flowers in a flowerbed without violating the "no adjacent flowers" rule. You are given an array flowerbed where 0 means empty and 1 means occupied. You can only plant a flower in an empty plot if both its left and right neighbors are also empty (or don't exist). This Can Place Flowers coding problem is a greedy logic task.

Why is this asked in interviews?

Companies like Google, Amazon, and Meta use this to test basic array iteration and edge-case handling. It evaluates if you can solve the problem in a single pass without needing complex data structures. The key challenge is handling the boundaries (first and last elements) where one neighbor is missing.

Algorithmic pattern used

This follows the Array, Greedy interview pattern.

1. Iterate through the array.
2. For each plot, check if it's 0 AND the left neighbor is 0 (or it's the first plot) AND the right neighbor is 0 (or it's the last plot).
3. If all conditions match, "plant" a flower (set to 1), decrement n, and move on.
4. If n <= 0, you've successfully placed all flowers.

Example explanation

flowerbed = [1, 0, 0, 0, 1], n = 1

1. Index 0: 1 (occupied).
2. Index 1: 0, but left neighbor is 1. Skip.
3. Index 2: 0, left neighbor is 0, right neighbor is 0. Plant! n becomes 0.
4. Done. Result: True. If n was 2, we couldn't place the second flower.

Common mistakes candidates make

• Modifying the array while iterating: This is actually the correct greedy approach, but some forget to update the current plot to '1', leading to overcounting (e.g., planting at index 2 and then again at index 3).
• Out of bounds errors: Not checking if i-1 or i+1 are valid indices before accessing them.
• Early exit: Not returning true as soon as n reaches 0.

Interview preparation tip

For greedy problems on arrays, always think about the "simplest valid move" you can make right now. For flowerbeds, planting as early as possible never hurts future chances, which is why the greedy approach works perfectly.