605. Can Place Flowers - Detailed Explanation
Problem statement
Description:
You are given a flowerbed represented as an integer array flowerbed containing 0's and 1's. A 0 means an empty plot, and a 1 means a plot that already holds a flower. Flowers cannot be planted in adjacent plots. Given an integer n, determine whether n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.
Example 1:
- Input:
- flowerbed =
[1, 0, 0, 0, 1] - n =
1
- flowerbed =
- Output:
true - Explanation:
You can plant a flower in the middle plot (index 2) to get[1, 0, 1, 0, 1].
Example 2:
- Input:
- flowerbed =
[1, 0, 0, 0, 1] - n =
2
- flowerbed =
- Output:
false - Explanation:
There is only one spot available to plant a new flower without violating the adjacent rule.
Example 3:
- Input:
- flowerbed =
[0, 0, 1, 0, 0] - n =
2
- flowerbed =
- Output:
true - Explanation:
One valid planting places flowers at indices 0 and 4, which gives[1, 0, 1, 0, 1]. Index 3 would be illegal, because it sits next to the existing flower at index 2. Checking both neighbors before planting is what prevents that mistake.
Constraints:
- 1 ≤ flowerbed.length ≤ 2 * 10⁴
- flowerbed[i] is 0 or 1
- There are no two adjacent flowers in flowerbed initially
- 0 ≤ n ≤ flowerbed.length
The technique here is a greedy single pass. You scan the flowerbed once, plant whenever a plot and both of its neighbors are empty, and never revisit a decision. Here a reading index i moves forward while the neighbor positions i-1 and i+1 decide whether the plot at i is usable. A separate counter records how many flowers you have placed. That arrangement is what lets a single sweep answer the question, and it recurs across the array patterns that interviewers reuse. Design Gurus teaches this exact problem in the Can Place Flowers lesson.
Hints
-
Hint 1:
Iterate through the array. At each empty plot, check whether its adjacent plots, or the boundaries, are empty. -
Hint 2:
Treat the boundaries carefully. If the plot sits at the start or the end of the array, you only need to check one neighbor. -
Hint 3:
When you plant a flower, mark that plot as planted by setting it to 1. Then skip the next plot, because it can no longer hold another flower.
Approaches
Approach 1: greedy iteration
- Idea:
Traverse the flowerbed. For each plot, check whether it is empty and whether its neighbors, where they exist, are also empty. If both hold, plant a flower by setting that plot to 1 and decrementn. Continue until the scan ends ornreaches 0. - Details:
- For index
i, check ifflowerbed[i] == 0. - For the left neighbor: if
i == 0orflowerbed[i-1] == 0. - For the right neighbor: if
i == flowerbed.length - 1orflowerbed[i+1] == 0. - If both conditions are true, plant a flower (
flowerbed[i] = 1) and skip the next index.
- For index
- Benefits:
This method is direct, and it runs in O(n) time with O(1) extra space. The greedy rule is safe because planting at the earliest legal plot never removes a later option.
Approach 2: simulation with in-place updates
- Idea:
Use a similar method to the greedy approach, but simulate the planting process more explicitly. Update the array in place and count the planted flowers. - Benefits:
This method matches the greedy approach in behavior and also uses constant extra space.
Code implementations
Python code
Java code
Complexity analysis
-
Time complexity:
The algorithm scans the flowerbed once, so the time complexity is O(n), where n is the length of the flowerbed. -
Space complexity:
The solution uses a constant amount of extra space, O(1).
Step-by-step walkthrough
-
Initialize a counter:
- Start with
count = 0to count the number of flowers planted.
- Start with
-
Iterate through the flowerbed:
- For each index
i, check whetherflowerbed[i]is 0, meaning an empty plot.
- For each index
-
Check neighbors:
- For the left neighbor, check whether
iis 0 orflowerbed[i-1]is 0. - For the right neighbor, check whether
iis the last index orflowerbed[i+1]is 0.
- For the left neighbor, check whether
-
Plant a flower:
- If both neighbor checks pass, set
flowerbed[i]to 1, which simulates planting a flower. - Increment the
countof planted flowers. - If
countreachesn, returntrue.
- If both neighbor checks pass, set
-
Finish the loop:
- After the scan ends, return
trueifcountis at leastn. Otherwise returnfalse.
- After the scan ends, return
Visual example
Consider the flowerbed [1, 0, 0, 0, 1] with n = 1:
-
Index 0:
Value is 1, so skip. -
Index 1:
Value is 0.- Left neighbor (index 0) is 1 → cannot plant here.
-
Index 2:
Value is 0.- Left neighbor (index 1) is 0 and right neighbor (index 3) is 0 → plant a flower here.
- Set
flowerbed[2] = 1and increment count to 1.
-
Since count equals n, return
true.
The updated flowerbed becomes [1, 0, 1, 0, 1].
Common mistakes
- Ignoring boundaries:
Failing to check whether the current index sits at the start or the end of the array can raise an index out-of-bounds error. - Not updating the array:
Forgetting to mark the plot as planted, by setting it to 1, leads to an incorrect count. - Overplanting:
Skipping the wrong number of plots after planting can place two flowers side by side, which violates the rule.
Edge cases
- No available spots:
When the flowerbed is full or nearly full, the algorithm should returnfalse. - n equals 0:
If no new flower needs to be planted, the function should returntrueimmediately. - A single-plot flowerbed:
Handle the case where the flowerbed contains only one plot, since that plot has no neighbor on either side.
Alternative variations and related problems
- Modified constraints:
Variants might set a different minimum gap between flowers, or introduce several types of flowers with their own rules. - Other greedy problems:
The same greedy reasoning applies to interval scheduling, seating arrangements, and resource allocation questions.
Related problems for further practice
- Gas Station
- Jump Game
- Container With Most Water
- Merge Intervals
Two more single-scan array questions pair well with this one. The answer to Product of Array Except Self comes out of a prefix pass and a suffix pass. In Reverse Words in a String, two indices mark the bounds of each word as you walk the string. Both, along with the rest of the array set, are taught in Grokking the Coding Interview.

GET YOUR FREE
Coding Questions Catalog

$98

$98

$197