Candy

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Children stand in a line, each with a rating. Give each child at least one candy, and give any child with a higher rating than a direct neighbour more candies than that neighbour. Return the minimum total number of candies. Neighbours with equal ratings have no constraint between them.

    A short problem with a sharp idea: each child has two constraints, one per side, and the trick is to satisfy them in two separate sweeps. It is a good test of whether you can argue that a greedy answer is both valid and minimal. Original problem: LeetCode 135.

    Example

    Each child who beats a neighbour gets more than that neighbour; the two children rated 2 can get different amounts because equal ratings set no rule.
    Each child who beats a neighbour gets more than that neighbour; the two children rated 2 can get different amounts because equal ratings set no rule.
    ratings = [1, 3, 4, 2, 2, 1]
    candies = [1, 2, 3, 1, 2, 1]
    Output: 10
    ratings = [5, 4, 3, 2, 1]
    Output: 15        # 5 + 4 + 3 + 2 + 1

    Constraints (assumed)

    • 1 ≤ n ≤ 2 × 10⁴; 0 ≤ rating ≤ 2 × 10⁴.

    What this question tests

    • Splitting a two-sided constraint into two one-sided passes.
    • Combining the passes with max so the second doesn't break the first.
    • Explaining why the result is minimal, not just valid.

    Questions to ask first

    1. What about equal neighbours? (Here: no rule; either can get more.)
    2. Is the line circular? (Here: no.)
    3. Do you need the distribution or only the total? (Here: the total.)
    4. Is O(n) extra space fine? (Yes; an O(1)-space version exists as a follow-up.)