Candy

Candy is the hardest problem in this section, and the reason is not the code. The rule looks at both neighbours at once, so any single left-to-right pass will satisfy one side and break the other. The trick is to stop fighting both sides together.

Satisfy the left neighbours in one pass. Satisfy the right neighbours in another. Then give each child the larger of the two. The same two-direction shape appears in Trapping Rain Water and Product of Array Except Self, so it is worth learning well.

The problem

Children stand in a row, each with a rating. Hand out sweets so that:

1. every child gets at least one sweet, and
2. a child with a strictly higher rating than an immediate neighbour gets more sweets than that neighbour.

Return the fewest sweets in total.

• [1, 3, 4, 5, 2] → 11. Give [1, 2, 3, 4, 1]. The child rated 5 needs more than the one rated 4, who needs more than 3, who needs more than 1.
• [2, 4, 3, 5, 1] → 7. Give [1, 2, 1, 2, 1]: each peak just needs one more than its valleys.

Constraints: 1 ≤ n ≤ 10⁵, ratings between 0 and 10⁵.

Clarifying questions

• Two neighbours with equal ratings? No constraint between them. [1, 2, 2] needs only [1, 2, 1] = 4.
• Only immediate neighbours? Yes.
• Is the row a circle? No — the ends have one neighbour each.
• Return the total or the distribution? The total.

Approach 1: the simple way

Give everyone one sweet. Sweep the row; whenever a child out-rates a neighbour but does not have more sweets, give them one more than that neighbour. Repeat full sweeps until nothing changes.

1def candy_brute(ratings: list[int]) -> int:2    """Start everyone at 1 and fix broken neighbours until nothing changes."""3    n = len(ratings)4    sweets = [1] * n5    changed = True6    while changed:7        changed = False8        for i in range(n):9            if i > 0 and ratings[i] > ratings[i - 1] and sweets[i] <= sweets[i - 1]:10                sweets[i] = sweets[i - 1] + 111                changed = True12            if i < n - 1 and ratings[i] > ratings[i + 1] and sweets[i] <= sweets[i + 1]:13                sweets[i] = sweets[i + 1] + 114                changed = True15    return sum(sweets)

It is correct: sweets only ever go up, and only to the smallest value that fixes a real violation. But it is O(n²) time. On a strictly falling row like [5, 4, 3, 2, 1], each left-to-right sweep can only settle one more child from the right, so it takes about n sweeps of n children. For n = 10⁵ that is 10¹⁰ steps.

The key insight

The rule has two halves that do not interfere:

• Left rule: if ratings[i] > ratings[i − 1], child i needs more than child i − 1.
• Right rule: if ratings[i] > ratings[i + 1], child i needs more than child i + 1.

Each half alone is easy. For the left rule, walk left to right: if you out-rate the child on your left, take one more than them; otherwise take 1. That gives each child the length of the rising run that ends at them — which is exactly the minimum the left rule forces, no more. Walk right to left for the right rule.

Now each child has two numbers: what the left side forces and what the right side forces. The larger of the two satisfies both — it is at least each requirement. And it is the smallest value that does, because each number is a real lower bound. Taking the maximum never breaks a neighbour's rule either. If child i out-rates the child on its right, that neighbour is not on a rising run from the left, so its left-pass value is just 1. Only its right-pass value can be large — and child i's right-pass value is already bigger. The mirror argument covers the left side.

This is greedy in the one-rule-at-a-time sense: each pass commits to the smallest count its rule allows, and never revisits it.

Approach 2: optimised — two passes

1def candy(ratings: list[int]) -> int:2    """Satisfy left neighbours, then right neighbours, keeping the larger need."""3    n = len(ratings)4    sweets = [1] * n5    for i in range(1, n):                      # left to right6        if ratings[i] > ratings[i - 1]:7            sweets[i] = sweets[i - 1] + 18    for i in range(n - 2, -1, -1):             # right to left9        if ratings[i] > ratings[i + 1]:10            sweets[i] = max(sweets[i], sweets[i + 1] + 1)11    return sum(sweets)

The second pass writes into the same array, taking the max in place. Because it walks right to left, sweets[i + 1] is already final when child i reads it.

Dry run on [1, 3, 4, 5, 2], showing each pass on its own and the final max:

Total 11. The right pass only matters at child 3 (rated 5, taller than the 2 on its right), and there the left pass already asks for more. On [1, 2, 3, 2, 1] the right pass wins at the peak instead: left gives [1, 2, 3, 1, 1], right gives [1, 1, 3, 2, 1], and the max is [1, 2, 3, 2, 1] = 9.

Complexity: O(n) time — two passes and a sum. O(n) space for the sweets array.

Approach 3: O(1) space, counting slopes

You can avoid the array by reading the row as up-slopes and down-slopes. On an up-slope, the k-th child up gets k + 1. On a down-slope, each new child at the bottom pushes the whole slope up by one, so the k-th step down adds k + 1. The only subtle part is the peak: it belongs to both slopes, and it needs one more sweet only when the down-slope grows longer than the up-slope that built it.

1def candy_constant_space(ratings: list[int]) -> int:2    """Count sweets slope by slope, without a sweets array."""3    if not ratings:4        return 05    total = 16    up = down = peak = 07    for prev, cur in zip(ratings, ratings[1:]):8        if cur > prev:                 # climbing: each step gets one more9            up += 110            peak = up11            down = 012            total += 1 + up13        elif cur == prev:              # flat: the chain resets to 114            up = down = peak = 015            total += 116        else:                          # falling: every child on the slope gets one more17            up = 018            down += 119            total += 1 + down20            if down <= peak:           # the peak is still tall enough21                total -= 122    return total

O(n) time, O(1) space. It passed the same 1,000 random tests as the two-pass version. In an interview, write the two-pass version first; offer this only if asked for constant space — its peak bookkeeping is easy to get wrong under pressure.

Edge cases

• One child: 1 sweet.
• All equal, [3, 3, 3]: no constraints, n sweets.
• Strictly falling, [5, 4, 3, 2, 1]: the right pass does all the work, [5, 4, 3, 2, 1] = 15.
• Plateaus, [1, 2, 2]: equal neighbours reset the run, so the second 2 gets 1.

Follow-ups

• The row is a circle? Start both passes at a child whose rating is a local minimum (it gets 1), and walk the circle from there.
• Equal neighbours must get equal sweets? Treat each run of equal ratings as one block that takes the maximum requirement of its members.
• Where else does this shape appear? Trapping Rain Water (highest bar to the left and right of each index) and Product of Array Except Self (product to the left and right) — both are "one pass each way, then combine".