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.

The tricky part is that each child has two neighbors (except the ones at the ends), and we need to satisfy the constraint in both directions simultaneously. 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 key observation is that "higher rating means more candies" only applies to strict inequality. If two adjacent children have the same rating, there's no requirement that they have the same (or different) candy count. This detail catches a lot of people off guard.

Key Constraints:

Intuition

The most straightforward idea: start by giving every child 1 candy, then keep scanning the array and fixing violations until there are none left. A violation is any position where a child has a higher rating than a neighbor but doesn't have more candies. When we find one, we bump that child's candy count up.

This is conceptually simple but wasteful. Each correction pass might introduce new issues (bumping one child might create a new violation with their other neighbor), so we might need multiple passes before everything stabilizes.

Algorithm

Example Walkthrough

Input:

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

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

Code

Each pass through the array might only resolve a small number of violations. What if we decomposed the two-directional constraint into two one-directional passes?

Intuition

The candy requirement is really two separate constraints glued together. 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 uses O(n) extra space. Can we compute the total without storing each child's candy count?

Intuition

If you look at the ratings array as a landscape, it's a series of "uphills" and "downhills." On an uphill (ratings increasing), candy counts go 1, 2, 3, ... On a downhill (ratings decreasing), candy counts go ..., 3, 2, 1. The question is what happens at the peaks.

We don't need to store every child's candy count. We can compute the total on-the-fly by tracking the lengths of ascending and descending runs. We track three values: up (ascending run length), down (descending run length), and peak (the ascending run length at the most recent peak). When the descending run exceeds peak, the peak child needs bumping, so we add 1 to the total.

Algorithm

Example Walkthrough

Code