44. Flowerbed Planner
A gardener has a row of plots described by bed, where 0 means the plot is empty and 1 means it already holds a plant. The existing plants are already spaced correctly: no two of them are in neighbouring plots.
The gardener wants to add n more plants. A new plant may only go into an empty plot whose left and right neighbours (where they exist) are both empty, so plants never end up side by side. Plots at either end of the row have just one neighbour.
Return true if all n new plants can be placed, otherwise false. A greedy left-to-right scan is enough.
Example 1
- Input:
- bed = [0,0,1,0,0,0,0], n = 3
- Output:
- true
- Explanation:
Plants can go in the first plot, the fifth plot and the last plot, so all 3 fit.
Example 2
- Input:
- bed = [0,0,1,0,0,0,0], n = 4
- Output:
- false
- Explanation:
At most 3 plants fit, so 4 cannot be placed.
Constraints
1 ≤ bed.length ≤ 2 * 104
bed[i] is 0 or 1, and no two 1s are adjacent
0 ≤ n ≤ bed.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)