Can Place Flowers
Asked at Atlassian
Problem
Given a flowerbed as a binary array where 1 means occupied and 0 means empty, decide whether n new flowers can be planted so no two flowers are adjacent. A one-pass greedy loop - the classic Atlassian entry point into the larger greedy family.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Easy | View all Atlassian questions → |
How to Think About It
Baseline: try every combination of n empty cells and test adjacency - exponential and unusable. The greedy insight is that a locally safe cell is also globally safe because planting only ever blocks its two immediate neighbors.
Key insight: a cell can accept a flower iff it is empty and both immediate neighbors are empty or out of bounds. Planting there can never make a future decision worse, so greedy is equal to optimal.
The loop: scan left to right. When you find a plantable cell, plant, increment the count, and keep scanning - setting the cell to 1 makes the following cell's "previous empty" test fail automatically.
Why the mutation does the bookkeeping: flipping the current cell to 1 automatically blocks the next cell from being planted, so the array modification implements the adjacency rule with no extra state.
Visual walkthrough for flowerbed = [1, 0, 0, 0, 1], n = 1:
- i=0: value 1, skip.
- i=1: value 0, previous is 1, blocked.
- i=2: previous 0, next 0, plant -> [1, 0, 1, 0, 1], count = 1.
- i=3: previous is 1, blocked. i=4: value 1, skip.
- count 1 >= n 1, return True.
Edge cases: an empty bed returns True only when n is 0; a single cell [0] can take one flower; boundary cells need just one empty neighbor because the missing side is out of bounds.
Optimal Approach
Scan the flowerbed left to right. Plant at a cell when it is 0 and both neighbors are 0 or out of bounds. Set the cell to 1, increment the count, and continue; the mutation automatically blocks the following cell from also being planted. Return true when the count reaches n.
Walkthrough for flowerbed = [1, 0, 0, 0, 1], n = 1:
- i=0: value 1, skip.
- i=1: value 0, previous is 1, blocked.
- i=2: previous 0 and next 0, plant. count = 1, bed becomes [1, 0, 1, 0, 1].
- i=3: previous is 1, blocked. i=4: value 1, skip.
- count = 1 >= 1, return true.
Time: O(n) space: O(1).
What Trips People Up in Real Interviews
Handling the boundaries incorrectly. The first and last cells have a single neighbor - index out of bounds, or treating the missing neighbor as occupied, wrongly blocks a valid end-cell plant. Default the out-of-bounds side to empty.
Mutating the array and not accounting for the effect on the next cell. The mutation is exactly what makes greedy work - after planting at i, cell i+1 is automatically blocked; state it out loud so the interviewer knows it is deliberate.
Forgetting the trivial cases. Return True immediately when n = 0, and return n == 0 for an empty bed. Scanners that skip these can crash or report False for a zero-plant request.
Comparing with count == n instead of >= n. Because the bed mutates as you scan, an equality comparison is fragile - use >= n (or return True the moment count reaches n) to stay robust.
Reaching for sliding windows or DP. A single left-to-right greedy pass is the intended answer; extra machinery reads as pattern matching rather than understanding the local rule.
Solution Code
def canPlaceFlowers(flowerbed, n):
count = 0
for i in range(len(flowerbed)):
if flowerbed[i] == 0:
prev_empty = i == 0 or flowerbed[i - 1] == 0
next_empty = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
if prev_empty and next_empty:
flowerbed[i] = 1
count += 1
return count >= nFrequently Asked Questions
What is the Can Place Flowers problem?
Given a flowerbed as a binary array where 1 means occupied and 0 means empty, decide whether n new flowers can be planted so no two flowers are adjacent. A one-pass greedy loop - the classic Atlassian entry point into the larger greedy family.
How do you solve Can Place Flowers?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Can Place Flowers?
Can Place Flowers is asked at Atlassian. It is a easy difficulty problem.
What are common mistakes on Can Place Flowers?
- Handling the boundaries incorrectly. The first and last cells have a single neighbor - index out of bounds, or treating the missing neighbor as occupied, wrongly blocks a valid end-cell plant. Default the out-of-bounds side to empty.
- Mutating the array and not accounting for the effect on the next cell. The mutation is exactly what makes greedy work - after planting at i, cell i+1 is automatically blocked; state it out loud so the interviewer knows it is deliberate.
- Forgetting the trivial cases. Return True immediately when n = 0, and return `n == 0` for an empty bed. Scanners that skip these can crash or report False for a zero-plant request.
- Comparing with `count == n` instead of `>= n`. Because the bed mutates as you scan, an equality comparison is fragile - use `>= n` (or return True the moment count reaches n) to stay robust.
- Reaching for sliding windows or DP. A single left-to-right greedy pass is the intended answer; extra machinery reads as pattern matching rather than understanding the local rule.