Can Place Flowers solution and explanation
Google
Cisco
9 more videos on this problem
Can Place Flowers - Leetcode 605 - PythonNeetCode · 10:34 · 66K views
Leetcode | 605. Can Place Flowers | Easy | Java SolutionDeveloper Docs · 4:36 · 5K views
Can Place Flowers - LeetCode 605 - Python #leetcode #leetcode75Deepti Talesra · 8:27 · 3K views
(Remade) Leetcode 605 - Can Place Flowers | ArrayNideesh Terapalli · 3:37 · 1K views
Can Place Flowers - LeetCode 605 - JavaScriptAlgoJS · 3:35 · 1K views
Can Place Flowers | Leetcode 605 | leetcode solutionEasyLeetcode · 7:22 · 1K views
605. Can Place Flowers | JavaScript | Array | LeetCode Daily ChallengeLeetCodeWithMonu · 8:16 · 954 views
605. Can Place Flowers - LeetCode Java SolutionCode with Carter · 9:51 · 589 views
Leetcode 605: Can Place Flowers | Step-by-Step SolutionMohit Chhabra · 14:25 · 395 views
Leetcode 605 - Can Place Flowers - Python Solution #leetcode #dataengineering #pythonData Engineering Studies · 6:07 · 316 views
The problem
You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.
Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1 Output: true
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2 Output: false
Constraints:
1 <= flowerbed.length <= 2 * 104flowerbed[i]is0or1.- There are no two adjacent flowers in
flowerbed. 0 <= n <= flowerbed.length
Approach overview
Problem Overview: You are given a binary array flowerbed where 1 means a flower is already planted and 0 means empty. You need to determine whether you can plant n new flowers without violating the rule that no two flowers can be adjacent.
Approach 1: Counting Possible Placements (O(n) time, O(1) space)
This method analyzes stretches of consecutive empty plots and calculates how many flowers can fit inside each segment. If you find a block of k zeros surrounded by planted flowers, the maximum placements inside that segment follow a predictable pattern: you can place (k-1)/2 flowers. Edge segments (start or end of the array) allow slightly more placements because only one side has a restriction. The algorithm scans the array once, counts zero segments, and accumulates the total possible placements. If the sum reaches or exceeds n, planting is feasible. The logic is purely arithmetic on segments, which keeps the time complexity O(n) and space complexity O(1). This technique works well when reasoning about contiguous gaps in an array.
Approach 2: Greedy Planting by Scanning (O(n) time, O(1) space)
The greedy approach directly simulates planting while scanning the array from left to right. For each index i, check three conditions: the current plot is empty, the left neighbor is empty (or doesn't exist), and the right neighbor is empty (or doesn't exist). If all conditions hold, plant a flower by setting flowerbed[i] = 1 and decrease n. This works because placing a flower as early as possible never blocks a better future placement. The algorithm only performs constant-time checks per position, so the total runtime is O(n) with O(1) extra space. This is a classic example of a greedy decision: a locally optimal placement leads to a globally optimal result.
During the scan you simply iterate once through the array, perform neighbor checks, and update the state when planting occurs. The modification is safe because once a flower is placed, the next index automatically becomes invalid for planting, which the neighbor checks naturally enforce.
Recommended for interviews: The greedy scanning approach is what interviewers typically expect. It shows you can reason about constraints directly and implement a linear pass with constant space. The counting approach demonstrates deeper pattern recognition with segments and boundaries, which can help when generalizing similar gap counting problems in array processing.
Approach 1: Greedy Planting by Scanning
This approach involves a single pass through the flowerbed array, considering each plot one by one. For each zero found, we check whether it's possible to plant a flower by ensuring that both neighboring plots (if they exist) are not planted. If it's possible, we plant the flower (i.e., change the zero to one) and reduce the count of n. The process stops early if n becomes zero. This greedy method ensures efficiency by trying to plant a flower at each opportunity.
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
for i in range(len(flowerbed)):
if flowerbed[i] == 0:
isPrevEmpty = (i == 0) or (flowerbed[i - 1] == 0)
isNextEmpty = (i == len(flowerbed) - 1) or (flowerbed[i + 1] == 0)
if isPrevEmpty and isNextEmpty:
flowerbed[i] = 1
n -= 1
if n == 0:
return True
return n <= 0class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 0) {
boolean isPrevEmpty = (i == 0) || (flowerbed[i - 1] == 0);
boolean isNextEmpty = (i == flowerbed.length - 1) || (flowerbed[i + 1] == 0);
if (isPrevEmpty && isNextEmpty) {
flowerbed[i] = 1;
n--;
if (n == 0) return true;
}
}
}
return n <= 0;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
for (int i = 0; i < flowerbed.size(); i++) {
if (flowerbed[i] == 0) {
bool isPrevEmpty = (i == 0) || (flowerbed[i - 1] == 0);
bool isNextEmpty = (i == flowerbed.size() - 1) || (flowerbed[i + 1] == 0);
if (isPrevEmpty && isNextEmpty) {
flowerbed[i] = 1;
n--;
if (n == 0) return true;
}
}
}
return n <= 0;
}
};var canPlaceFlowers = function(flowerbed, n) {
for (let i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] === 0) {
const isPrevEmpty = (i === 0) || (flowerbed[i - 1] === 0);
const isNextEmpty = (i === flowerbed.length - 1) || (flowerbed[i + 1] === 0);
if (isPrevEmpty && isNextEmpty) {
flowerbed[i] = 1;
n--;
if (n === 0) return true;
}
}
}
return n <= 0;
};#include <stdbool.h>
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
for (int i = 0; i < flowerbedSize; i++) {
if (flowerbed[i] == 0) {
bool isPrevEmpty = (i == 0) || (flowerbed[i - 1] == 0);
bool isNextEmpty = (i == flowerbedSize - 1) || (flowerbed[i + 1] == 0);
if (isPrevEmpty && isNextEmpty) {
flowerbed[i] = 1;
n--;
if (n == 0) return true;
}
}
}
return n <= 0;
}public class Solution {
public bool CanPlaceFlowers(int[] flowerbed, int n) {
for (int i = 0; i < flowerbed.Length; i++) {
if (flowerbed[i] == 0) {
bool isPrevEmpty = (i == 0) || (flowerbed[i - 1] == 0);
bool isNextEmpty = (i == flowerbed.Length - 1) || (flowerbed[i + 1] == 0);
if (isPrevEmpty && isNextEmpty) {
flowerbed[i] = 1;
n--;
if (n == 0) return true;
}
}
}
return n <= 0;
}
}The Python solution leverages list indexing to easily navigate and modify the flowerbed array. It succinctly checks and modifies the array to plant flowers, aiming to plant 'n' flowers while ensuring no adjacent flowers appear.
Time Complexity: O(m), where m is the length of the flowerbed.
Space Complexity: O(1), as it manipulates the array directly with no extra space needed.
Approach 2: Counting Possible Placements
This approach calculates the maximum number of flowers that can be planted by counting the stretches of zeros between planted flowers or array boundaries. For each encounter of a continuous stretch of zeros, determine how many flowers can be planted and accumulate this count until it reaches or exceeds n, or if it proves impossible.
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
count = 0
consecutiveZeros = 1 # pretend there is a zero at the start
for plot in flowerbed:
if plot == 0:
consecutiveZeros += 1
else:
count += (consecutiveZeros - 1) // 2
consecutiveZeros = 0
count += consecutiveZeros // 2 # pretend there is a zero at the end
return count >= nclass Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0, consecutiveZeros = 1;
for (int plot : flowerbed) {
if (plot == 0) {
consecutiveZeros++;
} else {
count += (consecutiveZeros - 1) / 2;
consecutiveZeros = 0;
}
}
count += consecutiveZeros / 2;
return count >= n;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0, consecutiveZeros = 1; // extra zero before start
for (int plot : flowerbed) {
if (plot == 0) {
consecutiveZeros++;
} else {
count += (consecutiveZeros - 1) / 2;
consecutiveZeros = 0;
}
}
count += consecutiveZeros / 2; // extra zero at the end
return count >= n;
}
};var canPlaceFlowers = function(flowerbed, n) {
let count = 0, consecutiveZeros = 1; // extra zero before start
for (let plot of flowerbed) {
if (plot === 0) {
consecutiveZeros++;
} else {
count += Math.floor((consecutiveZeros - 1) / 2);
consecutiveZeros = 0;
}
}
count += Math.floor(consecutiveZeros / 2); // extra zero at the end
return count >= n;
};#include <stdbool.h>
bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {
int count = 0, consecutiveZeros = 1; // extra zero before start
for (int i = 0; i < flowerbedSize; i++) {
if (flowerbed[i] == 0) {
consecutiveZeros++;
} else {
count += (consecutiveZeros - 1) / 2;
consecutiveZeros = 0;
}
}
count += consecutiveZeros / 2; // extra zero at the end
return count >= n;
}public class Solution {
public bool CanPlaceFlowers(int[] flowerbed, int n) {
int count = 0, consecutiveZeros = 1;
foreach (int plot in flowerbed) {
if (plot == 0) {
consecutiveZeros++;
} else {
count += (consecutiveZeros - 1) / 2;
consecutiveZeros = 0;
}
}
count += consecutiveZeros / 2;
return count >= n;
}
}The Python solution simplifies flower planting by viewing the entire process as counting potential spaces between rows of zeros, considering virtual zeros at the start and end. It calculates the necessary planting spots neatly without explicit in-place alteration.
Time Complexity: O(m), where m is the length of the flowerbed.
Space Complexity: O(1), since it operates within a fixed space usage.
Approach 3: Greedy
We directly traverse the array flowerbed. For each position i, if flowerbed[i]=0 and its adjacent positions on the left and right are also 0, then we can plant a flower at this position. Otherwise, we cannot. Finally, we count the number of flowers that can be planted. If it is not less than n, we return true, otherwise we return false.
The time complexity is O(n), where n is the length of the array flowerbed. We only need to traverse the array once. The space complexity is O(1).
function canPlaceFlowers(flowerbed: number[], n: number): boolean {
const m = flowerbed.length;
for (let i = 0; i < m; ++i) {
const l = i === 0 ? 0 : flowerbed[i - 1];
const r = i === m - 1 ? 0 : flowerbed[i + 1];
if (l + flowerbed[i] + r === 0) {
flowerbed[i] = 1;
--n;
}
}
return n <= 0;
}func canPlaceFlowers(flowerbed []int, n int) bool {
m := len(flowerbed)
for i, v := range flowerbed {
l, r := 0, 0
if i > 0 {
l = flowerbed[i-1]
}
if i < m-1 {
r = flowerbed[i+1]
}
if l+v+r == 0 {
flowerbed[i] = 1
n--
}
}
return n <= 0
}impl Solution {
pub fn can_place_flowers(flowerbed: Vec<i32>, n: i32) -> bool {
let (mut flowers, mut cnt) = (vec![0], 0);
flowers.append(&mut flowerbed.clone());
flowers.push(0);
for i in 1..flowers.len() - 1 {
let (l, r) = (flowers[i - 1], flowers[i + 1]);
if l + flowers[i] + r == 0 {
flowers[i] = 1;
cnt += 1;
}
}
cnt >= n
}
}class Solution {
/**
* @param Integer[] $flowerbed
* @param Integer $n
* @return Boolean
*/
function canPlaceFlowers($flowerbed, $n) {
array_push($flowerbed, 0);
array_unshift($flowerbed, 0);
for ($i = 1; $i < count($flowerbed) - 1; $i++) {
if ($flowerbed[$i] === 0) {
if ($flowerbed[$i - 1] === 0 && $flowerbed[$i + 1] === 0) {
$flowerbed[$i] = 1;
$n--;
}
}
}
return $n <= 0;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Planting by Scanning | Time Complexity: O(m), where m is the length of the flowerbed. |
| Counting Possible Placements | Time Complexity: O(m), where m is the length of the flowerbed. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Possible Placements | O(n) | O(1) | When analyzing zero segments or reasoning mathematically about placement capacity |
| Greedy Planting by Scanning | O(n) | O(1) | General case and most common interview solution using greedy checks |
Frequently asked questions
Is Can Place Flowers easy or hard?
Can Place Flowers is classified as an Easy problem on LeetCode. The main challenge is correctly handling boundary cases at the start and end of the array while applying a greedy placement rule.
Can Place Flowers Python/Java solution
Both Python and Java implementations follow the same greedy scan. Iterate through the array, check left and right neighbors, and plant when allowed. The logic is identical across Python, Java, C++, C#, and JavaScript with O(n) time and O(1) space complexity.
How to solve Can Place Flowers in O(n)?
Scan the flowerbed from left to right. For each index, check that the current position is 0 and both adjacent positions are also 0 (or out of bounds). If valid, plant a flower and decrement n. Continue until either n reaches zero or the array ends. This linear scan guarantees O(n) time and constant space.
What is the best approach for Can Place Flowers?
The greedy scanning approach is the most practical solution. Iterate through the array and plant a flower whenever the current plot and both neighbors are empty. Each placement updates the array and reduces the remaining flowers to plant. This runs in O(n) time with O(1) extra space and is the method most interviewers expect.
Is Can Place Flowers asked at Google/Amazon/Meta?
Variations of greedy array placement problems frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests basic greedy reasoning, edge case handling at boundaries, and careful array traversal.
What data structure is used in Can Place Flowers?
The problem primarily uses an array to represent the flowerbed. The solution relies on sequential iteration and neighbor checks rather than complex data structures, making it a straightforward greedy array problem.
What is the time complexity of Can Place Flowers?
The optimal solution runs in O(n) time because the flowerbed array is scanned once. Each position requires only constant-time neighbor checks. The space complexity is O(1) since the algorithm modifies the array in place and uses no additional data structures.