Saplings Along the Fence
EasyGreedyFree
Problem
A fence line is divided into beds; beds[i] is 1 if bed i already holds a tree and 0 if it is empty. Trees planted in adjacent beds compete for light, so no two trees may ever stand next to each other.
Return true if you can plant saplings new trees in empty beds without breaking the rule, false otherwise. The existing layout never breaks the rule.
Example 1
- Input:
- beds = [1, 0, 0, 0, 1], saplings = 1
- Output:
- true
Plant in bed 2: its neighbours, beds 1 and 3, are empty.
Example 2
- Input:
- beds = [1, 0, 0, 0, 1], saplings = 2
- Output:
- false
Only bed 2 is plantable; beds 1 and 3 touch existing trees.
Example 3
- Input:
- beds = [0, 0, 1, 0, 0], saplings = 2
- Output:
- true
Constraints
- 1 ≤ beds.length ≤ 2 · 10^4
- beds[i] is 0 or 1, with no two adjacent 1s
- 0 ≤ saplings ≤ beds.length
Hint
Show the first hint
When is a single empty bed plantable? Look only at its two neighbours.
Walkthrough
How to approach it
01Clarify before coding
- Do the ends of the fence have a neighbour outside? No: treat the outside as empty.
- Can saplings be 0? Yes, then the answer is true.
- May I modify beds? It is fine to work on a copy; the caller only needs the boolean.
02Brute force
Try every subset of empty beds of size saplings and check whether it keeps all trees non-adjacent.
Cost: O(C(z, saplings) · n) for z empty beds: exponential.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.