Candy

HardGreedy · Two Passes🧩 Greedy LeetCode #135 ↗Updated Oct 30, 2026

Problem

Children stand in a row and child i has score ratings[i]. Hand out candies so that every child gets at least one, and any child with a strictly higher score than a direct neighbour gets more candies than that neighbour. Return the smallest total number of candies needed.

Inputratings = [1,0,2]Output5 (2,1,2)

Inputratings = [1,2,2]Output4 (1,2,1)

Inputratings = [1,3,4,2,1]Output9 (1,2,3,2,1)

1 ≤ n ≤ 2·10⁴ · 0 ≤ ratings[i] ≤ 2·10⁴

Try it yourself

Java

class Solution {
    public int candy(int[] ratings) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Split the rule into two one-sided rules: a left-to-right pass satisfies “beat your left neighbour”, a right-to-left pass satisfies “beat your right neighbour”. Each child needs the max of the two — or, counting slopes, every rising and falling run is just 1+2+…+len.

PatternGreedy

Instinct An optimisation where one obvious local rule (earliest end, farthest reach, biggest first) never needs undoing - commit to it, then try hard to break it.

Memory hack Grab the best bite now and never look back - but only once a counterexample hunt fails to make you regret it.

Open the Greedy guide →

Approaches

Brute ForceRelax Until Stable

Time O(n²)Space O(n)

Give everyone 1 candy, then sweep the row repeatedly: whenever a child out-scores a neighbour but doesn't have more candy, bump them to neighbour + 1. Values only ever rise to the minimum they are forced to, so when a sweep changes nothing the total is minimal. A long descending run can need about n sweeps.

Java

public int candy(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;
}

Obviously correct, but quadratic on long monotone runs.

BetterTwo Passes (Left & Right Arrays)

Time O(n)Space O(n)

left[i] = length of the rising run ending at i (from the left), right[i] = same from the right. A child needs at least left[i] to satisfy the left rule and right[i] for the right rule, and max of the two satisfies both while staying minimal.

Java

public int candy(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;
}

Linear and easy to prove; the standard interview answer. Uses two O(n) arrays.

Pro tip

One array is enough: do the right-to-left pass in place with max.

OptimalSingle Pass Slope Counting

Time O(n)Space O(1)

Walk the row tracking the current rising length up, falling length down, and peak (the rise that led into the current fall). A rising step pays up + 1; a flat step resets and pays 1; a falling step pays down + 1 because every child in the fall shifts up by one — except the peak, which only grows once the fall gets longer than the rise.

Java

public int candy(int[] ratings) {
    int total = 1, up = 0, down = 0, peak = 0;
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {        // rising
            up++;
            peak = up;
            down = 0;
            total += up + 1;
        } else if (ratings[i] == ratings[i - 1]) { // flat: fresh start
            up = down = peak = 0;
            total += 1;
        } else {                                  // falling
            up = 0;
            down++;
            // the peak absorbs the extra candy until the fall outgrows it
            total += down + 1 - (peak >= down ? 1 : 0);
        }
    }
    return total;
}

Dry runratings = [1,0,2]

i current index changed

start
1
i
3

4

2

1

total=1
i=1
1

3
i
4

2

1

up=1, +2 → 3
i=2
1

3

4
i
2

1

up=2 peak=2, +3 → 6
i=3
1

3

4

2
i
1

down=1, +2-1 → 7
i=4
1

3

4

2

1
i
down=2, +3-1 → 9 ✔

O(1) memory in one pass; trickier to derive, so explain the peak rule carefully.

At a glance

Level	Approach	Time	Space
Brute Force	Relax Until Stable	`O(n²)`	`O(n)`
Better	Two Passes (Left & Right Arrays)	`O(n)`	`O(n)`
Optimal	Single Pass Slope Counting	`O(n)`	`O(1)`

Common pitfalls

Giving equal-rated neighbours equal candy is not required — equal ratings impose no rule.
Using one pass only — a single direction cannot see a longer run on the other side.
In the slope method, forgetting the peak adjustment double-counts or under-counts the top.

Interview tips

Decompose the two-sided rule into two one-sided rules — that's the real insight.
Prove minimality: each child gets exactly the length of its longest forced chain.
Offer the O(1) slope version only after the two-pass solution is solid.

Pattern

Two-directional greedy pass → a constraint depends on both neighbours: satisfy each side separately, then combine.

My notes saved in this browser