💬 Discord
Sign In
NeetCode #45LC-605EasyArrays & Hashing
← Back to All Problems

#45 · #605 · Can Place Flowers(种花问题)

📌 Problem Statement & Constraints

You have a long flowerbed in which some plots are planted and some are not, given as a binary array flowerbed. Flowers cannot be planted in adjacent plots. Given an integer n, return whether n new flowers can be planted without violating the adjacency rule. Constraints: 1 <= flowerbed.length <= 2 * 10^4, 0 <= n <= flowerbed.length.

💡 Core Algorithmic Approaches

  1. Greedy left-to-right planting is optimal: planting as early as possible never blocks a later opportunity more than any alternative would.
  2. A plot at index i can be planted if it is empty and both neighbours (with out-of-bounds treated as empty) are also empty.
  3. When you plant, mark flowerbed[i] = 1 so the next iteration sees the updated state -- this is what enforces the adjacency rule.
  4. Return early as soon as n reaches zero. The classic bug is an off-by-one on the left neighbour: the correct check is i == 0 or flowerbed[i-1] == 0.

💻 Benchmark Python3 Implementation

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        i = 0
        size = len(flowerbed)
        while i < size and n > 0:
            if flowerbed[i] == 0:
                left_ok = (i == 0 or flowerbed[i - 1] == 0)
                right_ok = (i == size - 1 or flowerbed[i + 1] == 0)
                if left_ok and right_ok:
                    flowerbed[i] = 1       # plant and mark
                    n -= 1
                    i += 2                 # skip the adjacent plot
                    continue
            i += 1
        return n == 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(size): one pass, with each plot examined once (planting jumps two steps ahead).
💾 Space Complexity
O(1) extra: the input is mutated in place, which the problem permits. If mutation is undesirable, track the previous value in a variable instead.

⚠️ Interview Pitfalls & Follow-ups

  • Checking i > 0 and flowerbed[i-1] == 0 without the i == 0 case: index 0 has no left neighbour, which is effectively empty, so it must be allowed. This is the most common bug.
  • Not updating flowerbed[i] = 1 after planting: adjacent plots would be wrongly considered plantable.
  • Jumping i += 2 after planting but also incrementing again: the loop's own increment must be skipped via continue.
  • Returning after the loop without checking n == 0: n may still be positive if the flowerbed ran out.