Can Place Flowers
Greedy single-pass — plant a flower whenever current, prev, and next are all 0.
3 min read
greedy array
Problem#
In flowerbed (0/1), can you plant n more flowers such that no two are adjacent?
Examples#
flowerbed = [1,0,0,0,1], n = 1→trueflowerbed = [1,0,0,0,1], n = 2→false
Constraints#
1 <= flowerbed.length <= 2 * 10^4.
Approach#
Walk left-to-right. Plant whenever flowerbed[i] == 0 and both neighbors (or virtual neighbors at the ends) are 0. Decrement n. Early-return on success.
Solution#
class Solution {public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { const int m = flowerbed.size(); for (int i = 0; i < m && n > 0; ++i) { if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == m - 1 || flowerbed[i + 1] == 0)) { flowerbed[i] = 1; --n; } } return n <= 0; }};func canPlaceFlowers(flowerbed []int, n int) bool { m := len(flowerbed) for i := 0; i < m && n > 0; i++ { if flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == m-1 || flowerbed[i+1] == 0) { flowerbed[i] = 1 n-- } } return n <= 0}from typing import List
class Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool: m = len(flowerbed) i = 0 while i < m and n > 0: if (flowerbed[i] == 0 and (i == 0 or flowerbed[i - 1] == 0) and (i == m - 1 or flowerbed[i + 1] == 0)): flowerbed[i] = 1 n -= 1 i += 1 return n <= 0var canPlaceFlowers = function(flowerbed, n) { const m = flowerbed.length; for (let i = 0; i < m && n > 0; i++) { if (flowerbed[i] === 0 && (i === 0 || flowerbed[i - 1] === 0) && (i === m - 1 || flowerbed[i + 1] === 0)) { flowerbed[i] = 1; n--; } } return n <= 0;};class Solution { public boolean canPlaceFlowers(int[] flowerbed, int n) { int m = flowerbed.length; for (int i = 0; i < m && n > 0; i++) { if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == m - 1 || flowerbed[i + 1] == 0)) { flowerbed[i] = 1; n--; } } return n <= 0; }}function canPlaceFlowers(flowerbed: number[], n: number): boolean { const m = flowerbed.length; for (let i = 0; i < m && n > 0; i++) { if (flowerbed[i] === 0 && (i === 0 || flowerbed[i - 1] === 0) && (i === m - 1 || flowerbed[i + 1] === 0)) { flowerbed[i] = 1; n--; } } return n <= 0;}Editorial#
Greedy is optimal because planting at the earliest opportunity never blocks a future placement (it only removes one position from consideration). Any “delay-and-plant-later” strategy is equally good or worse.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#