A garden bed is a row of plots, given as a string of 0 (empty) and 1 (already
planted). You want to plant k more plants so that no two plants are adjacent
(including the ones already there). Return true if that's possible.
positioningPlants(bed, k)
Input format: bed | k.
bed="10001", k=1 // → true
bed="10001", k=2 // → false
bed="00000", k=3 // → true
The constraint: no two plants adjacent. The question is whether deciding plot by plot, greedily, can be trusted to find the maximum plantings — or whether multiple arrangements need comparing.
An empty plot is safe to plant exactly when both immediate neighbors (or the bed's edge, which imposes no constraint) are also empty. Greedy: whenever you hit a safe, empty plot scanning left to right, plant there immediately rather than waiting for something "better."
Planting at the earliest available safe spot never blocks more future opportunities than skipping it would. Planting at position i only rules out i+1 — but you'd have to leave a gap somewhere nearby regardless, since the no-adjacent rule forces spacing no matter which plots you pick. Delaying buys no extra freedom and can only cost a planting if a safe opportunity gets blocked later by something else. Greedy is never worse than any alternative, which is what makes it optimal, not merely convenient.
Scan left to right. At each plot, check: is it empty, is the left neighbor empty (treating off-the-start as empty), is the right neighbor empty (same for off-the-end). All three true means plant there, mark filled, increment the count.
Stop as soon as the count reaches k — already shown possible. Reaching the end without hitting k means false.
Since greedy planting at the earliest opportunity is provably never worse, the greedy count equals the true maximum achievable — if greedy can't reach k, nothing can.
A single left-to-right scan does O(1) work per plot — O(n) time, O(n) space for a mutable copy (or O(1) tracking just "is the previous plot occupied").
def positioning_plants(bed, k):
plots = list(bed)
planted = 0
for i in range(len(plots)):
if plots[i] == "0":
left = i == 0 or plots[i - 1] == "0"
right = i == len(plots) - 1 or plots[i + 1] == "0"
if left and right:
plots[i] = "1"
planted += 1
if planted >= k:
return True
return planted >= k
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.