135. Candy — DSA Atlas

135

HardGreedy AlgorithmsGreedy neighbor constraintsTwo-pass greedy (left-to-right then right-to-left)

Candy

There are n children in a line, each with a rating given in the array ratings. Every child must get at least one candy, and any child with a higher rating than an immediate neighbor must receive more candies than that neighbor. Return the minimum total number of candies you must give out.

Open official problem prompt ↗

In plain English

Hand out the fewest candies possible while honoring 'higher rating than a neighbor means strictly more candy' in both directions.

Picture it like this

Like leveling a row of stacked blocks by walking the line twice: once forward raising each block above a shorter left neighbor, once backward raising it above a shorter right neighbor, then keeping whichever height each block needed.

Example

Input: ratings = [1, 0, 2]
Output: 5
Why: Give candies [2, 1, 2]: the middle child has the lowest rating and gets 1, and each higher-rated neighbor gets more, totaling 5.

Constraints

n == ratings.length1 <= n <= 2 * 10^40 <= ratings[i] <= 2 * 10^4

Pattern lesson

See the pattern, then code

Two-pass greedy (left-to-right then right-to-left)

↗

Greedy Algorithms

A locally best action can be justified by an exchange argument or invariant.. The left-neighbor rule and the right-neighbor rule are independent; satisfy each in its own sweep and take the maximum requirement per child so both rules hold at once.

New words, made simpleKnow these before the algorithm

left pass: Ensures every child outranking its left neighbor gets more candy than that neighbor.
right pass: Ensures every child outranking its right neighbor gets more candy, taking the max with the left result.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Repeated relaxation

Slow; may need many passes to converge.

Loop over the array adjusting candies until no rule is violated.

Time O(n^2)Space O(n)

Best choiceTwo-pass greedy

Linear and clean; the standard solution.

One left-to-right pass for left constraints, one right-to-left pass taking the max for right constraints.

Time O(n)Space O(n)

One-pass slope counting

Optimal in space but trickier to reason about; the two-pass form is preferred for clarity.

Track up/down slope lengths and add triangular-number contributions.

Time O(n)Space O(1)

The rule we keep true

Invariant

After the left pass, every ascending pair from the left is satisfied; after the right pass, candies[i] is at least one more than each strictly-lower neighbor on both sides.

Why this is correct

Reasoning

The left constraint (ratings[i] > ratings[i-1]) and right constraint (ratings[i] > ratings[i+1]) never conflict: the right pass only ever raises values via max, so it cannot break an already-satisfied left constraint. Taking the per-child maximum meets both with the smallest legal value.

The algorithm in three movesSay these aloud before coding

1Give every child 1 candy to start

start candy=[1,1,1]

2Left-to-right: if ratings[i] > ratings[i-1], set candy[i] = candy[i-1] + 1

L->R: [1,1,2]

3Right-to-left: if ratings[i] > ratings[i+1], set candy[i] = max(candy[i], candy[i+1] + 1)

R->L: [2,1,2] -> sum=5

4Sum the candy array

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readratings=[1,0,2]

2 · AskBaseline?

3 · Update statecandies=[1,1,1]

4 · ResultEveryone starts at 1.

Key takeaway

Ratings 1,0,2 resolve to candies 2,1,2 after the two greedy sweeps.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Baseline of one each
Guarantees the 'at least one candy' rule before any adjustments.
2
Lines 4-6Left pass
Rising ratings from the left force each child above its left neighbor.
3
Lines 7-9Right pass with max
Rising ratings from the right raise the child only if needed, never undoing the left pass.
4
Lines 10Total candies
Summing gives the minimum distribution satisfying both directions.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Strictly increasing ratings force 1,2,3,...,n
All equal ratings give exactly one candy each
A single child returns 1
A peak like [1,3,2] needs the peak to exceed both sides

Common beginner mistakes

Using assignment instead of max in the right pass, which erases left-pass requirements at peaks
Assuming equal adjacent ratings must differ in candy (they need not)
Only doing one pass, which ignores one of the two neighbor directions

Check your understanding

Why must the right pass use max(candies[i], candies[i+1] + 1) rather than a plain assignment?

Candy

Candy

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Greedy Algorithms