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.
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
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.