Candy
On this page
Problem statement
Children stand in a line, each with a rating. Give each child at least one candy, and give any child with a higher rating than a direct neighbour more candies than that neighbour. Return the minimum total number of candies. Neighbours with equal ratings have no constraint between them.
A short problem with a sharp idea: each child has two constraints, one per side, and the trick is to satisfy them in two separate sweeps. It is a good test of whether you can argue that a greedy answer is both valid and minimal. Original problem: LeetCode 135.
Example

ratings = [1, 3, 4, 2, 2, 1]
candies = [1, 2, 3, 1, 2, 1]
Output: 10
ratings = [5, 4, 3, 2, 1]
Output: 15 # 5 + 4 + 3 + 2 + 1
Constraints (assumed)
- 1 ≤ n ≤ 2 × 10⁴; 0 ≤ rating ≤ 2 × 10⁴.
What this question tests
- Splitting a two-sided constraint into two one-sided passes.
- Combining the passes with max so the second doesn't break the first.
- Explaining why the result is minimal, not just valid.
Questions to ask first
- What about equal neighbours? (Here: no rule; either can get more.)
- Is the line circular? (Here: no.)
- Do you need the distribution or only the total? (Here: the total.)
- Is O(n) extra space fine? (Yes; an O(1)-space version exists as a follow-up.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.