{ }SolveLogs
⌕
Home / Greedy / #605
LeetCode #605 Easy

Can Place Flowers

Can Place Flowers is LeetCode 605 (Easy). A flowerbed is an array where 1 is a planted plot and 0 an empty one. No two flowers may be in neighbouring plots. Given n, return true if n new flowers can be planted without breaking that rule.

  • The starting bed already follows the rule.
  • The first and last plots have only one neighbour.

The bed has up to 2 · 10⁴ plots, so one pass is the target.

Constraints
  • 1 <= flowerbed.length <= 2 * 10⁴
  • flowerbed[i] is 0 or 1.
  • There are no two adjacent flowers in flowerbed.
  • 0 <= n <= flowerbed.length
arraygreedy
Open on LeetCode ↗
02

Intuition

Scan from the left and plant at every plot you legally can. That never costs a flower later.

  • Why it is safe: everything to the left of plot i is already decided. Planting at i blocks only plot i + 1. Skipping i to plant at i + 1 instead would block i + 2, which is never better.
  • When a plot is legal: it is empty and both neighbours are empty. A neighbour that does not exist, before the first plot or after the last, counts as empty.

So the greedy scan plants the most flowers possible, and the answer is whether that count reaches n.

How to spot this pattern

A row of slots with a "no two neighbours" rule and a count to reach: take every legal slot from left to right. This greedy scan is safe for the same reason as the greedy scans in Assign Cookies, Non-overlapping Intervals and Jump Game: taking the earliest option never blocks more than skipping it.

03

Approach

Try it first

Before reading on: how many flowers fit in [0, 0, 0, 0, 0], and where? Then try [0, 0, 1, 0, 0] with n = 2: what does the first plot's left neighbour count as?

1

Scan the plots from left to right

Keep a count planted = 0. For each index i, skip the plot if it already holds a flower.

2

Read both neighbours, treating the ends as empty

For an empty plot, read left and right:

  • left = flowerbed[i - 1] if i > 0, else 0.
  • right = flowerbed[i + 1] if i is not the last index, else 0.

If either one is 1, the plot is blocked; move on. Outside the bed there is no flower, so a missing neighbour counts as empty.

3

Plant and write it into the bed

Both neighbours are empty, so set flowerbed[i] = 1 and add one to planted. Write the 1 into the bed so the next plot sees the new flower as its left neighbour.

4

Stop as soon as n flowers fit

If planted >= n, return true straight away; the rest of the bed cannot change the answer. If the scan ends first, return planted >= n.

04

Can Place Flowers solution in Python | C++ | Java

▶1class Solution:
▶2 def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
▶3 planted = 0
▶4 for i in range(len(flowerbed)):
▶5 if flowerbed[i] == 1:
▶6 continue
▶7 left = flowerbed[i - 1] if i > 0 else 0
▶8 right = flowerbed[i + 1] if i < len(flowerbed) - 1 else 0
▶9 if left == 1 or right == 1:
▶10 continue
▶11 flowerbed[i] = 1
▶12 planted += 1
▶13 if planted >= n:
▶14 return True
▶15 return planted >= n
bed1001020314checkleftplotrightplanted0n1planted = 0, need 1
planted0
n1
Start. Walk the plots from the left and plant wherever the rules allow. Planting early only ever blocks the next plot, so it never costs a flower later.
bed1i = 001020314checkleftplot1rightplanted0n1plot 0 has a flower → skip
flowerbed[0]1
planted0
n1
Plot 0 already holds a flower, so nothing can go here. Move on without reading the neighbours.
bed100i = 1020314checkleft1plot0right0planted0n1plot 1: left taken → blocked
left1
right0
planted0
n1
Plot 1 is empty, but the left neighbour has a flower. A flower here would sit next to it, so skip this plot.
bed10011i = 20314checkleft0plot1right0planted1n1plant at 2 → planted 1
left0
right0
planted1
n1
Both neighbours are empty, so plant at plot 2 and write a 1 there: the next plot will read it as its left neighbour.
bed1001120314checkleftplotrightplanted1n1planted 1 ≥ n 1 → return true
answertrue
planted1
n1
Return true. 1 new flower fits, which is what was asked. Nothing later in the bed can change that, so the scan stops here.
05

Common pitfalls

Counting a plot without planting it

✗ Wrong
if left == 0 and right == 0:
    planted += 1
✓ Right
if left == 0 and right == 0:
    flowerbed[i] = 1
    planted += 1

The next plot still sees an empty left neighbour and gets counted too, so two neighbouring flowers are counted. On [0, 0, 0] this counts 3 instead of 2, and returns true for n = 3.

Reading neighbours without checking the ends

✗ Wrong
if flowerbed[i - 1] == 0 and flowerbed[i + 1] == 0:
✓ Right
left = flowerbed[i - 1] if i > 0 else 0
right = flowerbed[i + 1] if i < len(flowerbed) - 1 else 0

At the last index i + 1 is out of range. At index 0, Python reads flowerbed[-1], the last plot, so [0, 0, 1] with n = 1 wrongly refuses plot 0 and returns false, with no error to warn you.

06

Edge cases

n = 0

Nothing needs planting. The scan may plant nothing, and planted >= n is 0 >= 0, so the answer is true.

A single empty plot, [0]

It has no neighbours at all, so both count as empty and one flower fits.

07

Complexity

Time
O(m)
Space
O(1)
m plots, each checked once with two neighbour reads; the bed is changed in place.
08

Can Place Flowers FAQ

Can you pad the flowerbed instead of checking the ends?

Yes. Build [0] + flowerbed + [0] and check plots 1 to m: now every real plot has two neighbours, so no bounds test is needed. It costs O(m) extra memory for the copy.

Is it fine to change the input array?

Yes, LeetCode does not check the array afterwards. If you must keep it unchanged, skip the plot after each new flower instead of writing a 1: after planting at i, jump to i + 2, since i + 1 is blocked anyway.

Is there a way to solve it without the greedy scan?

You can count runs of empty plots. A run of k empty plots between two flowers fits (k - 1) // 2 new ones; a run touching one end of the bed fits k // 2; a bed with no flowers at all fits (k + 1) // 2. Add these up and compare with n. It gives the same answer as the scan, with more cases to get right.

← Prev · #583
Delete Operation for Two Strings
Next · #617 →
Merge Two Binary Trees