Candy
Find the minimum number of candies to hand out so every child gets at least one and a child with a higher rating than a neighbor gets more, using two greedy passes.
Problem Understanding
Candy: n children stand in a line with ratings. Each child gets at least one candy, and a child with a higher rating than an adjacent child must get more candy than that neighbor. Return the minimum total.
Examples: [1,0,2] → 5 (2, 1, 2); [1,2,2] → 4 (1, 2, 1). Equal neighbors have no constraint between them.
The Intuition: One Rule per Direction
Split the condition into two independent rules and satisfy each with a greedy sweep:
- Left rule: a child rated above their left neighbor needs more than them. Sweeping left to right, set
candies[i] = candies[i - 1] + 1when it applies. - Right rule: the mirror image, sweeping right to left.
- Both at once: in the second sweep take the max with what the first gave, so the left rule survives.
Two opposite sweeps that combine information from both sides are also the idea in Product of Array Except Self and Trapping Rain Water.
Interactive Walkthrough
HIGHER RATING THAN A NEIGHBOUR → MORE CANDY
ONE EACH
ratings
candies
0
1
2
3
4
5
pass
:
so far
6
total
:
Every child starts with 1 candy
Next
Rating 1 is not above 3 on the left: child 1 keeps 1
ratings
Ratings are on top, candies below. The child being updated is filled, the neighbor it is compared with is marked, and a count the step raised is filled too. Watch the peak keep its 4 in the right pass.
Dry Run Table
Input: ratings = [3,1,2,3,4,2].
| Pass | candies |
|---|---|
| start | [1,1,1,1,1,1] |
| left → right | [1,1,2,3,4,1] |
| right → left | [2,1,2,3,4,1] |
In the right pass, child 4 (rating 4) needs only 2 against its right neighbor but keeps 4; child 0 (rating 3 > 1) rises to 2. Answer: 13.
The Solution Template
Two sweeps over one array.
Candy Code
1var candy = function(ratings) {2 const n = ratings.length;3 const candies = new Array(n).fill(1);4 for (let i = 1; i < n; i++) {5 if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;6 }7 for (let i = n - 2; i >= 0; i--) {8 if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);9 }10 return candies.reduce((a, b) => a + b, 0);11};
Edge Cases & Common Mistakes
- Equal ratings: no rule applies, so neighbors may differ freely;
[1,2,2]ends 1, 2, 1. - Overwriting in the second pass: use the max, or peaks lose candy.
- One child: answer 1.
- Strictly falling ratings: the left pass does nothing; the right pass does all the work.
- One pass only: fails on any falling run, e.g.
[2,1]needs 3, not 2.
Summary
Start everyone at 1. Sweep left to right giving one more than a lower-rated left neighbor, then right to left taking the max with one more than a lower-rated right neighbor, and sum. O(n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet