Candy
Children stand in a line with ratings. Each gets at least one candy, and any child rated higher than an immediate neighbour must get more candy than that neighbour. Return the minimum total.
Open on LeetCode ↗Intuition
Everyone tries one pass first, and one pass cannot work. The two rules — beat the left neighbour, beat the right neighbour — face opposite directions, and a descending run needs information about where the descent ends, which you have not read yet. So stop fighting it and satisfy them separately: one sweep per direction, then max(left[i], right[i]) per child, which is the smallest value satisfying both.
Two sweeps, one per direction. The left pass satisfies "higher rating than the left neighbour gets more candy"; the right pass does the same looking right. Taking the maximum at each index satisfies both simultaneously — a single pass can never see both constraints at once.
Approach
See why one pass fails
Sweeping left to right and incrementing on a rising rating handles ascending runs correctly, but a descending run needs the later child to have less, which you cannot know until you have seen where the descent ends. Any single-direction fix ends up patching values retroactively.
Two sweeps, one rule each
Initialise both arrays to all 1s, the minimum everyone is owed. Left to right: if ratings[i] > ratings[i-1] then left[i] = left[i-1] + 1. Right to left: if ratings[i] > ratings[i+1] then right[i] = right[i+1] + 1. Each pass now only looks in the direction it can actually resolve.
Combine with max, and see why it is minimal
Child i must satisfy both rules, so it needs at least left[i] and at least right[i] — hence at least their maximum. Assigning exactly the maximum satisfies both constraints simultaneously and gives no child more than required, so the sum is minimal. O(n) time and O(n) space; the space drops to O(1) with a slope-counting variant, but the two-array version is far easier to reason about under interview pressure.
Solution & live demo
Common pitfalls
Using a single left-to-right pass
for i in range(1, n):
if ratings[i] > ratings[i-1]: c[i] = c[i-1] + 1# left pass, then right pass, then max
A descending run like [5, 4, 3] needs candy counts that increase leftwards, which a forward pass can't produce — it only ever looks backwards. The reverse pass supplies exactly that missing constraint.
Summing rather than taking the max
return sum(left[i] + right[i] for i in range(n))
return sum(max(left[i], right[i]) for i in range(n))
Each child needs one count satisfying both neighbours, and the larger of the two already satisfies the smaller. Adding them double-counts the baseline candy every child receives.
Initialising the arrays to 0
left = [0] * n
left = [1] * n
Every child must receive at least one candy regardless of ratings. Starting at 0 lets flat runs receive nothing, violating the problem's floor.
Edge cases
Neither rule ever fires, so every child gets 1 and the total is n.
The left pass produces 1, 2, 3, ... and the right pass is all 1s; the max is the left pass.
The mirror case — the right pass carries the answer, which is exactly what a single left-to-right pass gets wrong.
The peak takes the larger of its two required values, which is precisely why the max step is needed rather than a sum.