Can Place Flowers

Greedy single-pass — plant a flower whenever current, prev, and next are all 0.

Easy
Time O(n) Space O(1)
LeetCode
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 = 1true
  • flowerbed = [1,0,0,0,1], n = 2false

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#

Can Place Flowers
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.