Candy
Candy is LeetCode 135 (Hard). n children stand in a line, and ratings[i] is the rating of child i. Hand out candies so that:
- every child gets at least one candy;
- a child with a higher rating than an adjacent child gets more candies than that neighbour.
Return the minimum total number of candies. Equal neighbours set no rule between them. With up to 2 · 10⁴ children, the answer has to come from a few linear passes.
- n == ratings.length
- 1 <= n <= 2 * 10⁴
- 0 <= ratings[i] <= 2 * 10⁴
Intuition
Each child has two rules: one with the left neighbour and one with the right neighbour. Candy LeetCode is rated Hard because a single sweep cannot keep both: raising one child can break the rule with a child you already passed.
So deal with one rule at a time:
- First pass, left to right: count candies using only the left-neighbour rule.
- Second pass, right to left: count candies using only the right-neighbour rule.
- Combine: each child gets the larger of its two counts. That keeps both rules true with as few candies as possible.
Use this when every position has a constraint against both neighbours: one sweep in each direction settles each side, and a max (or min) merges them. Trapping Rain Water uses the same idea with the tallest bar to the left and to the right, and Product of Array Except Self combines a prefix pass with a suffix pass.
Approach
Before reading on: for ratings = [1,2,5,4,3,2], give every child the fewest candies a left-to-right sweep allows. Which children break the rule against their right neighbour, and why can a second left-to-right sweep not fix the peak at 5?
Two ways to solve it
One sweep per neighbour, then each child takes the larger count.
- Logic: each pass checks a single rule.
- Proof: easy to argue in an interview.
- Memory: two arrays of length n.
The version most solutions teach and the one to write first.
Counts the length of each rising and falling run and adds 1 + 2 + ... as it goes.
- Memory: a few counters, no arrays.
- Peak: needs one extra candy when the fall outruns the rise.
- Risk: easy to get off by one.
The follow-up when O(1) space is asked for.
Both run in O(n) time. The two-pass candy solution is easier to get right, so the steps, the candy Python, C++ and Java code and the live demo follow it. The slope version saves memory; its code comes after the demo.
Start everyone at one candy
Fill left and right with 1. That is the minimum every child must get, and it is also the right value for any child that no rule pushes higher.
Left to right: the left-neighbour rule
For i from 1 up: if ratings[i] > ratings[i - 1], set left[i] = left[i - 1] + 1. The left neighbour's count is already settled when you reach i, so one more than it is exactly enough. Equal or lower ratings keep 1.
Right to left: the right-neighbour rule
For i from n - 2 down: if ratings[i] > ratings[i + 1], set right[i] = right[i + 1] + 1. Go right to left because a falling run such as 5, 4, 3 has to be counted from its low end, and a left-to-right sweep reaches the high end first.
Take the max for each child
Child i gets max(left[i], right[i]), and the answer is the sum. The larger value satisfies both rules at once, and anything smaller breaks one of them, so the total is the minimum. Three passes give O(n) time and O(n) space.
Candy solution in Python | C++ | Java
left[1] is already final, so this is safe.right[1] is final first; a falling run like 5, 4, 3 can only be counted from its low end.left[0] is already final, so this is safe.left[0] is already final, so this is safe.left[1] is already final, so this is safe.right[5] is final first; a falling run like 5, 4, 3 can only be counted from its low end.right[4] is final first; a falling run like 5, 4, 3 can only be counted from its low end.right[3] is final first; a falling run like 5, 4, 3 can only be counted from its low end.One pass over slopes
up is the length of the current rising run and down the length of the current falling run. A rising child gets up + 1 candies. Each new child on a fall adds down, because everyone already on that fall needs one more; the peak gets one extra only when the fall grows longer than the rise.
Common pitfalls
Using only a left-to-right pass
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
c[i] = c[i - 1] + 1# left pass, right pass, then max per child
A forward sweep only compares each child with the one before it. For [3, 2, 1] it gives everyone 1, but child 0 needs 3 and child 1 needs 2; the answer is 6, not 3.
Giving equal ratings more candy
if ratings[i] >= ratings[i - 1]:
if ratings[i] > ratings[i - 1]:
Only a strictly higher rating sets a rule. For [1, 2, 2] the last child may have 1 candy, fewer than its equal neighbour: the answer is 4, and >= returns 6.
Adding the two passes instead of taking the max
total += left[i] + right[i]
total += max(left[i], right[i])
Each child gets one count that must satisfy both rules, and the larger already satisfies the smaller. Adding them counts every child's base candy twice; [1, 0, 2] gives 8 instead of 5.
Edge cases
No rating is strictly higher than a neighbour, so everyone keeps 1 and the answer is n.
Only the right-to-left pass raises anything: the counts run n, n − 1, …, 1, totalling n(n + 1) / 2.
Complexity
Candy FAQ
Why is LeetCode 135 a greedy problem?
Each pass makes the smallest choice the rule allows, one more than the neighbour or else 1, and never revisits it. Taking the max of two minimal answers is still minimal, so the greedy choices add up to the smallest total.
Can the two arrays share one array?
Yes. Run the left pass into candies, then in the right pass set candies[i] = max(candies[i], candies[i + 1] + 1). The max is essential: a plain assignment would erase what the left pass found.