Topics › Greedy Algorithms › Medium/Hard

Candy

Hard TUF ID 544 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

n children stand in a line, and child i has rating ratings[i]. Hand out candies so that:

• every child gets at least one candy, and
• a child whose rating is strictly higher than an immediate neighbour gets strictly more candies than that neighbour.

Return the minimum total number of candies. Equal ratings impose nothing: two neighbours with the same rating may get any amounts.

Constraints: 1 ≤ n ≤ 2 × 10^4, 0 ≤ ratings[i] ≤ 2 × 10^4.

Example 1

ratings = [1, 0, 2]
answer = 5               // candies [2, 1, 2]

The middle child has the lowest rating and gets 1; both neighbours out-rate it and need 2.

Example 2

ratings = [1, 2, 2]
answer = 4               // candies [1, 2, 1]

The second child beats the first, so it needs 2. The third child has the same rating as the second, so 1 is enough.

Approach 1: Brute force, repair until stable

Intuition. Start everyone at one candy and look for a broken rule: a child who out-rates a neighbour but does not have more candies. Raise that child to neighbour + 1 and keep sweeping until a whole pass changes nothing.

Every raise is forced, never generous. Take any valid assignment opt. Initially 1 ≤ opt[i]. When we raise child i because it out-rates neighbour j, the new value is candies[j] + 1 ≤ opt[j] + 1 ≤ opt[i], because opt must give i more than j. So candies never exceeds any valid assignment, and when the sweeps stop every rule holds. A valid assignment that is pointwise no larger than every other valid one is the minimum.

Algorithm.

1. Fill candies with 1.
2. Repeat: sweep i from left to right; if i out-rates its left neighbour without having more, set candies[i] = candies[i-1] + 1; do the same against the right neighbour. Stop when a sweep changes nothing.
3. Return the sum.

static int bruteForce(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < n; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
                candies[i] = candies[i - 1] + 1;
                changed = true;
            }
            if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
                candies[i] = candies[i + 1] + 1;
                changed = true;
            }
        }
    }
    int total = 0;
    for (int c : candies) total += c;
    return total;
}

Complexity. Time O(n^2): a left-to-right sweep fixes an increasing run completely, but a decreasing run like [5, 4, 3, 2, 1] gains only one correct child per sweep (from the right end), so up to n sweeps of n steps each. Space O(n) for the candy array.

Approach 2: Better, two passes

Intuition. The rule “beat a lower-rated neighbour” is really two independent rules: beat your left neighbour, and beat your right neighbour. Each one is trivial on its own.

• left[i]: the fewest candies satisfying only the left rule. Walk left to right: if ratings[i] > ratings[i-1] then left[i] = left[i-1] + 1, otherwise 1. This is just one more than the length of the strictly increasing run ending at i.
• right[i]: the same from the other side, walking right to left.

Child i needs at least max(left[i], right[i]), since each rule alone forces its own value. And giving exactly that maximum satisfies both rules. Suppose ratings[i] > ratings[i-1]. Then right[i-1] = 1 (child i-1 does not out-rate child i), so child i-1 receives max(left[i-1], 1) = left[i-1], while child i receives at least left[i] = left[i-1] + 1. The right rule is symmetric. So the sum of maxima is both necessary and sufficient.

Algorithm.

1. Fill left and right with 1.
2. For i = 1..n-1: if ratings[i] > ratings[i-1], left[i] = left[i-1] + 1.
3. For i = n-2..0: if ratings[i] > ratings[i+1], right[i] = right[i+1] + 1.
4. Return the sum of max(left[i], right[i]).

static int better(int[] ratings) {
    int n = ratings.length;
    int[] left = new int[n], right = new int[n];
    Arrays.fill(left, 1);
    Arrays.fill(right, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
    }
    int total = 0;
    for (int i = 0; i < n; i++) total += Math.max(left[i], right[i]);
    return total;
}

Dry run on [1, 0, 2]:

Total 5.

Complexity. Time O(n): three linear passes. Space O(n) for the two helper arrays. (You can drop right by computing it on the fly in the second pass with a single variable, which brings space down to one array.)

Approach 3: Optimal, counting slopes in O(1) space

Intuition. Picture the ratings as a mountain range: flat steps, up-slopes and down-slopes. The candies on each slope are fully determined.

• On an up-slope, each child gets one more than the previous: 2, 3, 4, … above the base.
• On a down-slope of k children after a peak, the bottom child gets 1, the one above it 2, and so on up to k. Since we only need the total, we can add 1, 2, …, k while walking down; the sum is the same in either order.
• The peak belongs to both slopes. It got peak candies from the climb, but it must also beat the first child of the descent, who holds k. After the down loop, down equals k + 1, exactly what the peak needs. If down > peak, add the difference.
• A flat step (equal ratings) resets: the next child can start at 1.

The bottom of a descent got 1, and it is also the base of the next climb, which is why peak restarts at 1 for every new slope.

Algorithm.

1. If the array is empty return 0. Give child 0 one candy: total = 1, i = 1.
2. While i < n:
   • If ratings[i] == ratings[i-1]: add 1, advance, continue.
   • Climb: peak = 1; while rising, peak++, add peak, advance.
   • Descend: down = 1; while falling, add down, advance, down++.
   • If down > peak, add down - peak.
3. Return total.

static int optimal(int[] ratings) {
    int n = ratings.length;
    if (n == 0) return 0;
    int total = 1, i = 1;                                  // child 0 gets 1 candy for now
    while (i < n) {
        if (ratings[i] == ratings[i - 1]) {                // flat step: no rule applies, restart at 1
            total += 1;
            i++;
            continue;
        }
        int peak = 1;
        while (i < n && ratings[i] > ratings[i - 1]) {     // climbing: 2, 3, 4, ...
            peak++;
            total += peak;
            i++;
        }
        int down = 1;
        while (i < n && ratings[i] < ratings[i - 1]) {     // descending: count 1, 2, 3, ... from the bottom
            total += down;
            i++;
            down++;
        }
        if (down > peak) total += down - peak;             // the peak must beat the longer side
    }
    return total;
}

Dry run on [1, 3, 2, 1] (the descent is longer than the climb):

Final candies are [1, 3, 2, 1], total 7. Without the fix, the peak would hold 2 while its right neighbour also holds 2, breaking the rule.

Complexity. Time O(n): every index is advanced exactly once by one of the loops. Space O(1): a handful of counters.

Edge cases and pitfalls

• Equal ratings. The rule is strict. [1, 2, 2] needs 4, not 6; treating >= as > overcounts. In Approach 3, a flat step resets to 1, and a flat peak like [1, 2, 2, 1] correctly gives [1, 2, 2, 1], total 6.
• The peak correction. Forgetting if (down > peak) undercounts every long descent; adding the peak twice (once on the climb and once on the descent) overcounts.
• Monotone arrays. [1, 2, 3, 4, 5] and [5, 4, 3, 2, 1] both need 1 + 2 + ... + 5 = 15. They are good tests for each loop on its own.
• Single child or empty input. One candy, or zero.
• Overflow. The worst total is n(n + 1) / 2 ≈ 2 × 10^8 for n = 2 × 10^4, which fits in an int.

Related problems

• Trapping Rainwater uses the same “one pass from each side, combine per index” idea.
• Assign Cookies is a gentler greedy about handing out the fewest resources.
• Lemonade Change is another single-scan greedy with local decisions.
• Job sequencing Problem is a harder greedy in the same section.