Planting Along a Garden Row

Easy

A row of garden beds beds runs along a fence: 1 means the bed already holds a shrub, 0 means it is empty. Shrubs in neighbouring beds crowd each other's roots, so no two shrubs may stand side by side, and right now the row respects that. The gardener has seedlings new plants. Return True if all of them can go into empty beds while keeping the no-neighbours rule, and False otherwise. The beds at either end have a neighbour on one side only.

Example 1

beds=[0, 0, 1, 0, 0, 0, 0], seedlings=3 → True

Plant in beds 0, 4 and 6: none of them sits next to an occupied bed.

Example 2

beds=[1, 0, 0, 1, 0], seedlings=1 → False

Beds 1 and 2 both touch an occupied bed, and so does bed 4. There is no room.

Example 3

beds=[0], seedlings=1 → True

Constraints

1 ≤ len(beds) ≤ 2 · 10⁴
beds[i] is 0 or 1
beds never has two 1s in a row
0 ≤ seedlings ≤ len(beds)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array

Similar problems

Cake Slices for Guests Easy Strength of the Weaker Partner Easy Making Change at the Kiosk Easy Rise and Fall Lineup Easy Triangle From Sticks Easy

Input

beds=[0, 0, 1, 0, 0, 0, 0], seedlings=3

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.