We have a line of children, each with a rating. We need to hand out candies so that every child gets at least one, and any child whose rating is strictly higher than an immediate neighbor gets more candies than that neighbor. The goal is to minimize the total number of candies.

Each child except the two at the ends has two neighbors, so the constraint must hold in both directions at once. If child 3 has a higher rating than both child 2 and child 4, then child 3's candy count must exceed both of those neighbors.

The rule "higher rating means more candies" applies only to strict inequality. If two adjacent children have the same rating, neither is required to get more than the other, so both can receive a single candy.

Key Constraints:

Intuition

Give every child 1 candy, then repeatedly scan the array and fix violations until none remain. A violation is a position where a child has a higher rating than a neighbor but does not have more candies. The fix raises that child's count to the neighbor's count plus one.

Each correction can create a new violation against the corrected child's other neighbor, so several passes may be needed before the array stabilizes.

Algorithm

Example Walkthrough

Input:

Pass 1: Check each child. Child 0 has rating 1 > child 1's rating 0 and candies[0]=1 <= candies[1]=1, so raise candies[0] to 2. Child 2 has rating 2 > child 1's rating 0 and candies[2]=1 <= candies[1]=1, so raise candies[2] to 2. Result:

Pass 2: No violations found. Done. Total = 2 + 1 + 2 = 5.

Code

The repeated passes redo work that two directed passes can settle once: one forward pass for the left-neighbor constraint, one backward pass for the right-neighbor constraint.

Intuition

The candy requirement combines two independent constraints. The left constraint says: if ratings[i] > ratings[i-1], then candies[i] > candies[i-1]. The right constraint says: if ratings[i] > ratings[i+1], then candies[i] > candies[i+1].

A left-to-right pass can enforce the left constraint perfectly, because by the time we reach position i, we've already finalized position i-1. Similarly, a right-to-left pass can enforce the right constraint. At each position, the answer is the maximum of what the two passes require, because we need to satisfy both constraints simultaneously.

Algorithm

Example Walkthrough

Code

The two-pass approach is O(n) time, which is optimal, but it stores a full candies array. The final approach computes the total in a single pass with O(1) extra space.

Intuition

Read left to right, the ratings form a sequence of uphills and downhills. On an uphill (ratings increasing), the minimum candy counts are 1, 2, 3, ... On a downhill (ratings decreasing), they count back down to 1. The two slopes interact only at the peak between them, which must clear both sides: it needs max(up, down) + 1 candies, where up and down are the lengths of the slopes on either side.

This structure lets us compute the total without storing per-child counts. We track three values: up (current ascending run length), down (current descending run length), and peak (the ascending run length at the most recent peak). Going up, the new child gets up + 1 candies. Going down, the new child gets 1 candy and every child already on the downhill needs one more candy than before, which comes to down candies in total, so adding down at each step applies the retroactive increases without revisiting the array. Once down exceeds peak, each further step also forces one more candy onto the peak itself, so we add 1 extra. Equal adjacent ratings break the slope: the new child gets 1 candy and all three counters reset.

Algorithm

Example Walkthrough

Code