605. Can Place Flowers
Asked at Atlassian, LinkedIn
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Array
Companies
2
Problem
You are given an array flowerbed that describes a row of plots. A 1 means a plot already has a flower, and a 0 means the plot is empty. You are also given an integer n.
Flowers may not be planted in two plots that touch each other. In other words, after you plant, no two 1s may sit side by side.
Return true if you can plant at least n new flowers without breaking that rule, and false otherwise. The input bed is guaranteed to already follow the rule, so you only need to worry about the flowers you add.
Where can a new flower go?
Constraints
- ●
1 <= flowerbed.length <= 2 * 10^4 - ●
flowerbed[i] is 0 or 1 - ●
There are no two adjacent flowers in flowerbed - ●
0 <= n <= flowerbed.length
Examples
flowerbed = [1,0,0,0,1], n = 1trueflowerbed = [1,0,0,0,1], n = 2falseAsked At
2 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Easy | View all Atlassian questions → |
| Easy | View all LinkedIn 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.
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).
Greedy left-to-right scan
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Can Place Flowers?
Can Place Flowers is asked at Atlassian, LinkedIn. 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.