Problem statement

n children stand in a line with ratings. You distribute candies such that:

• Every child gets at least one candy.
• A child with a higher rating than an adjacent child gets more candies than that neighbor.

Return the minimum total number of candies.

Example 1

Input: ratings = [1,0,2]
Output: 5
Explanation: Give 2, 1, 2 candies.

Example 2

Input: ratings = [1,2,2]
Output: 4
Explanation: Give 1, 2, 1 — equal ratings need no relation.

Constraints

• 1 <= ratings.length <= 30
• 0 <= ratings[i] <= 100

Hints for Candy

1. Hint 1

   Two passes: left-to-right fixes rising edges, right-to-left fixes falling edges.

2. Hint 2

   Take the max of both constraints at each position.

How to solve Candy

Each child faces two separate demands: beat the neighbour on the left if you outrank them, and beat the neighbour on the right if you outrank them. Trying to satisfy both at once in a single pass is where this problem traps people. Handle them in two independent sweeps and take the larger requirement at each position.

Approach

1. Give every child 1 candy — the floor everyone is entitled to.
2. Sweep left to right: if ratings[i] > ratings[i-1], set candy[i] = candy[i-1] + 1. This satisfies every rising edge.
3. Sweep right to left: if ratings[i] > ratings[i+1], set candy[i] = max(candy[i], candy[i+1] + 1). This satisfies every falling edge.
4. Sum the array.

Why it works

The max is what makes the two sweeps compose. The left sweep produces the smallest values satisfying all left-neighbour constraints; the right sweep does the same on the right. Taking the maximum satisfies both, and cannot be lowered anywhere — each value is forced by one of the two constraints or is the minimum of 1. So the result is simultaneously valid and minimal at every index, hence minimal in total. Crucially the second sweep never breaks the first, because it only ever increases values, and raising a child never violates a constraint that says they must exceed a neighbour.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The right-to-left sweep must take a max, not an assignment — plain assignment destroys the left sweep's work on peaks.
• Equal ratings impose no constraint at all; both children may hold 1.
• One combined pass cannot work: a rising run's height depends on how far back it started, which you only learn later.
• Start everyone at 1, not 0 — every child must get at least one candy.

Reference solution

Python

from typing import List

def candy(ratings: List[int]) -> int:
    n = len(ratings)
    candies = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    return sum(candies)

Java

public static int candy(int[] ratings) {
    int n = ratings.length;
    int[] give = new int[n];
    Arrays.fill(give, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) give[i] = give[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && give[i] <= give[i + 1]) give[i] = give[i + 1] + 1;
    }
    int total = 0;
    for (int i = 0; i < n; i++) total += give[i];
    return total;
}

C++

int candy(vector<int>& ratings) {
    int n = (int) ratings.size();
    vector<int> give(n, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) give[i] = give[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1] && give[i] <= give[i + 1]) give[i] = give[i + 1] + 1;
    }
    int total = 0;
    for (int i = 0; i < n; i++) total += give[i];
    return total;
}

JavaScript

var candy = function(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    }
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
    return candies.reduce(function(a, b) { return a + b; }, 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard