Can Place Flowers
Easy · Greedy · Array · Greedy
Problem
A long flowerbed is given as a list flowerbed of plots: 0 is an empty plot and 1 a plot that already has a flower. Flowers may not grow in adjacent plots, and the bed you are given already follows that rule.
Given a number n, return true if n new flowers can be planted without any two flowers ending up next to each other, and false otherwise.
Examples
Input: flowerbed = [0,0,1,0,0], n = 2 Output: true
Plant in the first and the last plot; each has only one neighbor, and it is empty.
Input: flowerbed = [1,0,0,0,1], n = 2 Output: false
Only the middle plot has empty plots on both sides, so one flower fits, not two.
Input: flowerbed = [0], n = 1 Output: true
One plot with no neighbors at all takes a flower.
Constraints
- 1 <= len(flowerbed) <= 2 · 10^4
- flowerbed[i] is 0 or 1
- no two adjacent plots are both 1
- 0 <= n <= len(flowerbed)
Approaches
- Baseline: rescan from the start for each flower — time O(n · L), space O(L)
Follow-up
The same pass gives the largest number of flowers the bed can take, not just yes or no. Without walking: a run of z empty plots between two flowers takes (z − 1) // 2, a run touching one end takes z // 2, and an all-empty bed takes (L + 1) // 2.
Related problems
Start free on Cariara · Coding problems · System design studio
