DSA AnimatorDSA animations
Candy LC #135 Hard Greedy · Two-Pass
Problem

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subject to two requirements: every child must have at least one candy, and children with a higher rating than their adjacent neighbors must get more candies. Return the minimum number of candies needed.

Example 1
Input: ratings = [1,0,2]
Output: 5
Explanation: Give candies [2,1,2] — the child at index 0 (rating 1) has more than neighbor at index 1 (rating 0). Child at index 2 (rating 2) has more than neighbor at index 1.
Example 2
Input: ratings = [1,2,2]
Output: 4
Explanation: Give candies [1,2,1] — the middle child has a higher rating than left, so gets more. The last child has the same rating as middle, so just 1 candy is fine.
Constraints: 1 ≤ ratings.length ≤ 2×10⁴  |  0 ≤ ratings[i] ≤ 2×10⁴
Try Examples
Custom ratings:
Approach
Two-Pass Greedy — Satisfy Both Neighbor Constraints
Pass 1 (L→R) handles left neighbors. Pass 2 (R→L) handles right neighbors — take max to not break Pass 1.
Candy Distribution Arena
Load an example to begin.
Variables
Phase
—
Index i
—
ratings[i]
—
c[i]
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
Total so far
—
🍬
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Initialize all c[i] = 1 (every child gets at least 1 candy)
2
Pass 1 (L→R): if ratings[i] > ratings[i-1] → c[i] = c[i-1] + 1
3
Pass 2 (R→L): if ratings[i] > ratings[i+1] → c[i] = max(c[i], c[i+1] + 1)
4
Return sum(c) — minimum candies satisfying all constraints
Time
O(n)
Space
O(n)
Why Two Passes Work

A single left-to-right pass only ensures every child has more candy than their left neighbor when needed. The right-to-left pass then ensures the right neighbor constraint. Taking the max during Pass 2 preserves whatever Pass 1 already set — guaranteeing both constraints are satisfied simultaneously with the minimum total.

How to solve Candy

LeetCode 135 · Hard · Greedy · Pattern: Two-Pass Greedy

Why the obvious approach is slow

Repeatedly fixing violations until none remain can take O(n²). Each child really has two separate rules, one for the left neighbour and one for the right.

The key idea

Give everyone 1 candy to start. Left to right, if a rating is higher than the left neighbour, give one more than that neighbour. Right to left, if a rating is higher than the right neighbour, take the bigger of its value and the right neighbour plus 1.

Remember

Split a two-sided rule into two one-sided passes. Take the maximum so both rules hold.

Run the animation above on your own input, or watch the 1:25 video explanation of Candy with a dry run and Java code.

More Greedy problems