Domain 1EasyCORE

Can Place Flowers

The problem asks us to determine whether we can plant `n` new flowers in a given flowerbed without violating the rule that no two flowers can be planted in adjacent plots. The input is an integer array `flowerbed` where each element is either `0` (empty) or `1` (not empty). The output should be a boolean indicating whether it's possible to plant `n` flowers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Greedy

605. Can Place Flowers

Model: qwen2.5-coder:14b
Topics: Array,Greedy
FAANG asked: 1
Acceptance rate: 31.7%


Problem Breakdown

The problem asks us to determine whether we can plant n new flowers in a given flowerbed without violating the rule that no two flowers can be planted in adjacent plots. The input is an integer array flowerbed where each element is either 0 (empty) or 1 (not empty). The output should be a boolean indicating whether it’s possible to plant n flowers.

Inputs:

  • flowerbed: An array of integers (0s and 1s).
  • n: An integer representing the number of new flowers to plant.

Outputs:

  • A boolean value (true or false).

Implicit Constraints/Edge Cases:

  • If n is 0, we should return true immediately since no planting is required.
  • If the flowerbed length is 1 and it’s empty ([0]), we can plant a flower if n is 1.
  • The flowerbed might be entirely full or entirely empty.
  • The flowerbed could have an odd or even number of plots.

Intuition

A brute-force approach would involve checking every possible position in the flowerbed to see if planting a flower there would violate the no-adjacent-flowers rule. This approach is inefficient because it doesn’t take advantage of any patterns or constraints that can simplify the problem.

The key insight is to realize that we only need to check each plot once and decide whether to plant a flower based on its neighbors. If a plot is empty and both its left and right neighbors are also empty (or out of bounds), then we can plant a flower there. This greedy approach ensures that we make the best decision at each step without looking ahead, leading to an optimal solution.

Approach

  1. Initialization: Start by checking if n is 0. If so, return true immediately since no planting is needed.
  2. Iterate through the flowerbed: For each plot in the flowerbed:
    • Check if the current plot is empty (flowerbed[i] == 0).
    • Check if the left neighbor is empty or out of bounds (i == 0 or flowerbed[i-1] == 0).
    • Check if the right neighbor is empty or out of bounds (i == len(flowerbed) - 1 or flowerbed[i+1] == 0).
  3. Plant a flower: If all conditions are met, plant a flower in the current plot by setting flowerbed[i] = 1 and decrement n.
  4. Check if done: After iterating through the flowerbed, check if n has been reduced to 0. If so, return true; otherwise, return false.

Complexity Analysis

  • Time Complexity: O(m), where m is the length of the flowerbed array. We iterate through the array once.
  • Space Complexity: O(1). We use a constant amount of extra space.

Solution

def canPlaceFlowers(flowerbed, n):
    if n == 0:
        return True
    
    for i in range(len(flowerbed)):
        if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed) - 1 or flowerbed[i+1] == 0):
            flowerbed[i] = 1
            n -= 1
            if n == 0:
                return True
    
    return False

Edge Cases Handled

  • Empty flowerbed (flowerbed = [0], n = 1): The code correctly identifies that one flower can be planted.
  • Full flowerbed (flowerbed = [1,1,1,1], n = 1): The code correctly identifies that no flowers can be planted.
  • Single plot flowerbed (flowerbed = [0], n = 0): The code immediately returns true since no planting is needed.
  • Multiple plots with alternating empty and full (flowerbed = [0,1,0,1,0], n = 2): The code correctly identifies that two flowers can be planted.