Candy

Distribute the fewest candies satisfying neighbour constraints, by sweeping left then right

HardGreedy (two passes)

ArrayGreedy

Problem Statement

n children stand in a line, each with a rating. Distribute candies subject to two rules:

Every child gets at least one candy.
A child with a higher rating than an immediate neighbour gets more candies than that neighbour.

Return the minimum total number of candies.

Input:  ratings = [1, 0, 2]
Output: 5
Why:    candies = [2, 1, 2]

Input:  ratings = [1, 2, 2]
Output: 4
Why:    candies = [1, 2, 1]
        The last two children have EQUAL ratings, so neither
        needs more than the other.

Intuition

The trap is trying to satisfy both neighbours at once. Fixing a child relative to the left can break the constraint on the right, and fixing that can break the next one — an endless ripple.

The key insight — split one hard constraint into two easy ones

Rule 2 is really two independent rules:

Left rule: if ratings[i] > ratings[i-1] then candies[i] > candies[i-1]
Right rule: if ratings[i] > ratings[i+1] then candies[i] > candies[i+1]

Each rule alone is trivially satisfiable in a single directional sweep. Then take the maximum of the two results per child — a value that satisfies both requirements simultaneously, and is the smallest such value.

Why the maximum is both valid and minimal

Valid: the left sweep's requirement for child i depends only on i-1, and the right sweep's depends only on i+1. Taking the max is at least each requirement, so both hold.
Minimal: each child's count is exactly the larger of two hard lower bounds. Going below either would break a rule, so nothing smaller is possible.

Real-world analogy

Adjusting a row of picture frames so each is higher than any shorter neighbour. Do one pass left to right fixing every leftward violation, then one pass right to left fixing every rightward violation — keeping whichever height is greater at each spot. Two disciplined sweeps beat endless local nudging.

Watch it run

Pass 1 — left to right, enforcing the left rule on ratings = [1, 0, 2, 5, 3, 1]

ratings[1,0,2,5,3,1]

Everyone starts with 1 candy — rule 1 is satisfied by construction.

1 / 5

Pass 2 — right to left, taking the max at each position

Start from the right end. The last child has no right neighbour — unchanged at 1.

1 / 5

The second sweep only ever raises values, so the first sweep's guarantees survive.

Approach

Give everyone 1 candy

This satisfies rule 1 and establishes the floor.

Left-to-right sweep

For i from 1 to n-1: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1.

Right-to-left sweep

For i from n-2 down to 0: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).

The max is what preserves the left sweep's work.

Return the sum

The second sweep must use `max`, not plain assignment

Writing candies[i] = candies[i+1] + 1 would overwrite a larger value earned in the first pass and break the left constraint.

For ratings = [1, 3, 2]: the left pass gives [1, 2, 1]. At i = 1 the right rule needs candies[2] + 1 = 2. Plain assignment would also give 2 here, but with ratings = [1, 5, 4, 3, 2] the left pass builds up a large value at index 1 that a plain assignment would destroy. max keeps both constraints alive.

Solution

def candy(ratings: list[int]) -> int:
    """Fewest candies satisfying both neighbour rules."""
    n = len(ratings)
    candies = [1] * n   # rule 1: everyone gets at least one

    # Pass 1: satisfy the left-neighbour rule.
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Pass 2: satisfy the right-neighbour rule without losing pass 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)

Equal ratings impose no constraint at all

Rule 2 only fires on a strictly higher rating. With ratings = [1, 2, 2] the third child needs nothing relative to the second, so [1, 2, 1] is valid and totals 4. Using >= anywhere would inflate the answer — this is the most common wrong reading of the problem.

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Time — three linear passes (two sweeps plus the sum).
Space — the candies array. A one-pass O(1)-space solution exists that counts ascending and descending run lengths, but it is considerably harder to get right and rarely worth it.

Edge Cases

Trapping Rain Water — the same left-sweep / right-sweep / combine structure
Product of Array Except Self — prefix and suffix passes over one array
Gas Station — greedy reasoning with a correctness proof

Candy

A single child

All ratings equal, e.g. [3, 3, 3]

Strictly increasing, e.g. [1, 2, 3, 4]

Strictly decreasing, e.g. [4, 3, 2, 1]

A peak in the middle, e.g. [1, 3, 2]

On this page