LeetCode 605: Can Place Flowers (Greedy Neighbor Check)
LeetCode 605GreedyArrayToday we solve LeetCode 605 - Can Place Flowers.
Source: https://leetcode.com/problems/can-place-flowers/
English
Problem Summary
Given a flowerbed array with 0 (empty) and 1 (already planted), determine whether we can plant n new flowers without violating the rule that no two adjacent plots can both contain flowers.
Key Insight
If position i is empty, and both neighbors (if they exist) are also empty, planting at i is always safe and locally optimal. Greedily planting as early as possible never hurts future choices because planting only blocks immediate neighbors, and those neighbors could not both be used anyway.
Algorithm
1) Traverse the flowerbed from left to right.
2) At each index i, check:
- flowerbed[i] == 0
- i == 0 || flowerbed[i-1] == 0
- i == m-1 || flowerbed[i+1] == 0
3) If all true, plant there (flowerbed[i] = 1) and increment planted count.
4) If planted count reaches n, return true early.
5) After loop, return whether planted count is at least n.
Complexity Analysis
Time: O(m), where m is flowerbed length.
Space: O(1).
Common Pitfalls
- Forgetting boundary handling for first/last plot.
- Planting without updating the array, which causes incorrect next checks.
- Missing early return when n == 0 or when target is already reached.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0) return true;
int planted = 0;
int m = flowerbed.length;
for (int i = 0; i < m; i++) {
if (flowerbed[i] == 1) continue;
int left = (i == 0) ? 0 : flowerbed[i - 1];
int right = (i == m - 1) ? 0 : flowerbed[i + 1];
if (left == 0 && right == 0) {
flowerbed[i] = 1;
planted++;
if (planted >= n) return true;
}
}
return planted >= n;
}
}func canPlaceFlowers(flowerbed []int, n int) bool {
if n == 0 {
return true
}
planted := 0
m := len(flowerbed)
for i := 0; i < m; i++ {
if flowerbed[i] == 1 {
continue
}
left := 0
if i > 0 {
left = flowerbed[i-1]
}
right := 0
if i < m-1 {
right = flowerbed[i+1]
}
if left == 0 && right == 0 {
flowerbed[i] = 1
planted++
if planted >= n {
return true
}
}
}
return planted >= n
}class Solution {
public:
bool canPlaceFlowers(vector& flowerbed, int n) {
if (n == 0) return true;
int planted = 0;
int m = static_cast(flowerbed.size());
for (int i = 0; i < m; ++i) {
if (flowerbed[i] == 1) continue;
int left = (i == 0) ? 0 : flowerbed[i - 1];
int right = (i == m - 1) ? 0 : flowerbed[i + 1];
if (left == 0 && right == 0) {
flowerbed[i] = 1;
planted++;
if (planted >= n) return true;
}
}
return planted >= n;
}
}; class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True
planted = 0
m = len(flowerbed)
for i in range(m):
if flowerbed[i] == 1:
continue
left = 0 if i == 0 else flowerbed[i - 1]
right = 0 if i == m - 1 else flowerbed[i + 1]
if left == 0 and right == 0:
flowerbed[i] = 1
planted += 1
if planted >= n:
return True
return planted >= n/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function(flowerbed, n) {
if (n === 0) return true;
let planted = 0;
const m = flowerbed.length;
for (let i = 0; i < m; i++) {
if (flowerbed[i] === 1) continue;
const left = (i === 0) ? 0 : flowerbed[i - 1];
const right = (i === m - 1) ? 0 : flowerbed[i + 1];
if (left === 0 && right === 0) {
flowerbed[i] = 1;
planted++;
if (planted >= n) return true;
}
}
return planted >= n;
};中文
题目概述
给定一个花坛数组，0 表示空位，1 表示已种花。要求判断是否可以再种下 n 朵花，并且不能出现相邻两格都种花的情况。
核心思路
从左到右贪心扫描：当且仅当当前位置为空，且左右相邻（若存在）都为空时，就在当前位置种花。这种“尽早种”的策略是安全的，因为一次种植只会影响相邻两格，而相邻两格本来也不可能同时被选中。
算法步骤
1）从左到右遍历数组。
2）对位置 i 检查三件事：当前位置是 0、左邻是 0（或越界）、右邻是 0（或越界）。
3）若满足则种花（写回 flowerbed[i] = 1），并计数 +1。
4）若计数已达到 n，可提前返回 true。
5）遍历结束后判断计数是否至少为 n。
复杂度分析
时间复杂度：O(m)，其中 m 是花坛长度。
空间复杂度：O(1)。
常见陷阱
- 忽略首尾边界，导致访问越界或判断错误。
- 种花后不写回数组，后续判断会失真。
- 忘记处理 n == 0 的直接成立场景。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
if (n == 0) return true;
int planted = 0;
int m = flowerbed.length;
for (int i = 0; i < m; i++) {
if (flowerbed[i] == 1) continue;
int left = (i == 0) ? 0 : flowerbed[i - 1];
int right = (i == m - 1) ? 0 : flowerbed[i + 1];
if (left == 0 && right == 0) {
flowerbed[i] = 1;
planted++;
if (planted >= n) return true;
}
}
return planted >= n;
}
}func canPlaceFlowers(flowerbed []int, n int) bool {
if n == 0 {
return true
}
planted := 0
m := len(flowerbed)
for i := 0; i < m; i++ {
if flowerbed[i] == 1 {
continue
}
left := 0
if i > 0 {
left = flowerbed[i-1]
}
right := 0
if i < m-1 {
right = flowerbed[i+1]
}
if left == 0 && right == 0 {
flowerbed[i] = 1
planted++
if planted >= n {
return true
}
}
}
return planted >= n
}class Solution {
public:
bool canPlaceFlowers(vector& flowerbed, int n) {
if (n == 0) return true;
int planted = 0;
int m = static_cast(flowerbed.size());
for (int i = 0; i < m; ++i) {
if (flowerbed[i] == 1) continue;
int left = (i == 0) ? 0 : flowerbed[i - 1];
int right = (i == m - 1) ? 0 : flowerbed[i + 1];
if (left == 0 && right == 0) {
flowerbed[i] = 1;
planted++;
if (planted >= n) return true;
}
}
return planted >= n;
}
}; class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n == 0:
return True
planted = 0
m = len(flowerbed)
for i in range(m):
if flowerbed[i] == 1:
continue
left = 0 if i == 0 else flowerbed[i - 1]
right = 0 if i == m - 1 else flowerbed[i + 1]
if left == 0 and right == 0:
flowerbed[i] = 1
planted += 1
if planted >= n:
return True
return planted >= n/**
* @param {number[]} flowerbed
* @param {number} n
* @return {boolean}
*/
var canPlaceFlowers = function(flowerbed, n) {
if (n === 0) return true;
let planted = 0;
const m = flowerbed.length;
for (let i = 0; i < m; i++) {
if (flowerbed[i] === 1) continue;
const left = (i === 0) ? 0 : flowerbed[i - 1];
const right = (i === m - 1) ? 0 : flowerbed[i + 1];
if (left === 0 && right === 0) {
flowerbed[i] = 1;
planted++;
if (planted >= n) return true;
}
}
return planted >= n;
};
Comments