How do you solve Can Place Flowers?

Iterate through the flowerbed array. For each empty plot, check if the left and right neighbors are empty or out of bounds. If so, plant a flower by setting the plot to 1 and decrement n. If at any point n reaches zero, return true immediately. After the loop, return whether n is less than or equal to zero.

What pattern does Can Place Flowers use?

The Pattern: Greedy (Local Optimal Placement) The Heuristic: When constraints depend only on immediate neighbors, a left-to-right greedy scan that plants at the first valid spot ensures maximum placements without violating adjacency.

Can Place Flowers | Greedy

Q: What is the time complexity of Can Place Flowers?

O(m). The algorithm performs a single pass through the flowerbed array of length m, checking neighbors and updating state in constant time per element.

Problem

Given an integer array flowerbed containing 0's and 1's, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule.

1 ≤ flowerbed.length ≤ 2 * 10⁴
flowerbed[i] is 0 or 1
There are no two adjacent flowers in the initial flowerbed
0 ≤ n ≤ flowerbed.length

Example

Input: flowerbed = [1,0,0,0,1], n = 1

Output: true

The flowerbed has empty plots at indices 1, 2, and 3. The algorithm scans from left to right. At index 1, the left neighbor is occupied (index 0), so it cannot plant here. At index 2, both neighbors (indices 1 and 3) are empty, so it plants a flower here, reducing n from 1 to 0. Since n reaches 0, the algorithm returns true immediately, confirming that planting is possible without violating adjacency.

Approach

Straightforward Solution

A brute-force approach might try all combinations of planting flowers, checking adjacency after each attempt, which is exponential and infeasible for large inputs.

Core Observation

The fundamental truth is that a flower can only be planted in a plot if both its immediate neighbors are empty or out of bounds (for edge plots). This local condition ensures no two flowers are adjacent.

Path to Optimal

Preview

The key insight is to greedily plant flowers at the earliest possible empty plot that satisfies the adjacency condition. By scanning left to right and planting whenever possible, the algorithm maximizes the number of flowers planted without violating the rule…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through the flowerbed array. For each empty plot, check if the left and right neighbors are empty or out of bounds…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m)

The algorithm performs a single pass through the flowerbed array of length m, checking neighbors and updating state in constant time per element.

Space

O(1)

The algorithm modifies the input array in place and uses only a fixed number of variables, resulting in constant auxiliary space.

Solution

Python

1class Solution:
  def canPlaceFlowers(self, flowerbed: list[int], n: int) -> bool:
      for i in range(len(flowerbed)):
          if flowerbed[i] == 0:
              left_empty = i == 0 or flowerbed[i - 1] == 0
              right_empty = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
7
              if left_empty and right_empty:
                  flowerbed[i] = 1
                  n -= 1
11
                  if n == 0:
                      return True
14
      return n <= 0

Step-by-Step Solution

1

Scan Flowerbed and Greedily Plant Flowers at Valid Positions

3for i in range(len(flowerbed)):
  if flowerbed[i] == 0:
      left_empty = i == 0 or flowerbed[i - 1] == 0
      right_empty = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0
      if left_empty and right_empty:
          flowerbed[i] = 1
          n -= 1
          if n == 0:
              return True

Objective

To iterate through the flowerbed and plant flowers greedily at plots where both neighbors are empty or out of bounds, decrementing n accordingly.

Key Insight

By checking the left and right neighbors for each empty plot, the algorithm ensures no adjacency violation occurs. Planting immediately when possible maximizes the number of flowers planted because it prevents missing early opportunities that could block later placements. This local decision-making is sufficient because the problem's constraints are strictly local (adjacent plots only).

Interview Quick-Check

Core Logic

The algorithm checks if the current plot is empty and both neighbors are empty or out of bounds, then plants a flower and decrements n.

State & Boundaries

Edge plots are handled by treating out-of-bound neighbors as empty, allowing planting at the ends if valid.

Common Pitfalls & Bugs

Failing to update the flowerbed array after planting can cause incorrect multiple plantings in the same spot.

Complexity

The single pass with constant-time neighbor checks ensures O(m) time and O(1) space.

2

Return Whether All Flowers Were Successfully Planted

To return true if all required flowers have been planted (n <= 0), otherwise false.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

if left_empty and right_empty:

Check if both left and right neighbors are empty or out of bounds, allowing planting.

This condition enforces the no-adjacent-flowers rule by ensuring planting does not violate adjacency constraints.

Line 9 Critical

flowerbed[i] = 1

Plant a flower at the current plot by setting it to 1.

Updating the flowerbed array prevents future iterations from planting adjacent flowers, maintaining correctness.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does greedily planting flowers at the earliest valid spot guarantee the maximum number of flowers planted without adjacency violations?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Can Place Flowers from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Can Place Flowers drill

or drill a free problem

1	`class Solution:`
2	`def canPlaceFlowers(self, flowerbed: list[int], n: int) -> bool:`
3	`for i in range(len(flowerbed)):`
4	`if flowerbed[i] == 0:`
5	`left_empty = i == 0 or flowerbed[i - 1] == 0`
6	`right_empty = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0`
7
8	`if left_empty and right_empty:`
9	`flowerbed[i] = 1`
10	`n -= 1`
11
12	`if n == 0:`
13	`return True`
14
15	`return n <= 0`

3	`for i in range(len(flowerbed)):`
4	`if flowerbed[i] == 0:`
5	`left_empty = i == 0 or flowerbed[i - 1] == 0`
6	`right_empty = i == len(flowerbed) - 1 or flowerbed[i + 1] == 0`
8	`if left_empty and right_empty:`
9	`flowerbed[i] = 1`
10	`n -= 1`
12	`if n == 0:`
13	`return True`