Can Place Flowers — Solution in Python, Java & C++
Can Place Flowers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and greedy.
Can Place Flowers is an easy coding problem on arrays and greedy, asked in Amazon, Microsoft, Adobe and Atlassian interviews.
- Difficulty: Easy
- Topics: Arrays, Greedy
- Asked at: Amazon, Microsoft, Adobe, Atlassian, Nutanix, LinkedIn
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have a long flowerbed in which some plots are planted and some are not. Flowers cannot be planted in adjacent plots.
Given an integer array flowerbed containing 0s (empty) and 1s (planted), and an integer n, return true if n new flowers can be planted without violating the adjacency rule.
Example 1
Input: flowerbed = [1,0,0,0,1], n = 1
Output: true
Explanation: The middle plot can take one flower.
Example 2
Input: flowerbed = [1,0,0,0,1], n = 2
Output: false
Example 3
Input: flowerbed = [0,0,1,0,0], n = 2
Output: true
Constraints
1 <= flowerbed.length <= 40flowerbed[i] is 0 or 1.There are no two adjacent flowers in the input.0 <= n <= 20
Hints for Can Place Flowers
Hint 1
Scan left to right and plant greedily whenever a plot is empty and both neighbours are empty.
Hint 2
Treat positions before the start and after the end as empty, so the two ends are not special cases in disguise.
Hint 3
Planting as early as possible is optimal — an earlier flower never blocks more plots than a later one.
How to solve Can Place Flowers
Greedy left to right: plant in any empty plot whose neighbours are empty, treating out-of-range positions as empty.
Approach
- Walk the bed; at
i, plant ifbed[i] == 0,i == 0 or bed[i-1] == 0, andi == last or bed[i+1] == 0. - Mark the plot planted and count.
- Return
planted >= n.
Why it works
Planting at the earliest legal plot never hurts: it blocks only i + 1, and any optimal arrangement that skips i for i + 1 can swap to i without losing a flower. Repeating the exchange shows greedy is maximal.
Complexity
- Time —
O(n) - Space —
O(1) if mutating a copy
Pitfalls
- Forgetting to mark the plot after planting lets the next plot plant adjacent to it.
- Stop early once
planted >= nif you like — the count only grows.
Reference solution
Python
def canPlaceFlowers(flowerbed, n) -> bool:
bed = list(flowerbed)
planted = 0
for i in range(len(bed)):
if bed[i] == 0 and (i == 0 or bed[i - 1] == 0) and (i == len(bed) - 1 or bed[i + 1] == 0):
bed[i] = 1
planted += 1
return planted >= nJava
public static boolean canPlaceFlowers(int[] flowerbed, int n) {
int[] bed = Arrays.copyOf(flowerbed, flowerbed.length);
int planted = 0;
for (int i = 0; i < bed.length; i++) {
if (bed[i] == 0 && (i == 0 || bed[i - 1] == 0) && (i == bed.length - 1 || bed[i + 1] == 0)) {
bed[i] = 1;
planted++;
}
}
return planted >= n;
}C++
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
vector<int> bed = flowerbed;
int planted = 0;
int len = (int) bed.size();
for (int i = 0; i < len; i++) {
if (bed[i] == 0 && (i == 0 || bed[i - 1] == 0) && (i == len - 1 || bed[i + 1] == 0)) {
bed[i] = 1;
planted++;
}
}
return planted >= n;
}JavaScript
var canPlaceFlowers = function(flowerbed, n) {
const bed = flowerbed.slice();
let planted = 0;
for (let i = 0; i < bed.length; i++) {
if (bed[i] === 0 && (i === 0 || bed[i - 1] === 0) && (i === bed.length - 1 || bed[i + 1] === 0)) {
bed[i] = 1;
planted++;
}
}
return planted >= n;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms