Candy
HardTwo passes, one each direction
Problem
Children in a line have ratings. Each gets >=1 candy and a child with a higher rating than a neighbor gets more candy than that neighbor. Return the minimum total candies.
Sweep left giving more than a smaller left neighbour, then sweep right doing the same — take the max.
The idea
Sweep left to right giving a child more candy than its left neighbour when its rating is higher, then sweep right to left doing the same for the right neighbour, taking the maximum of the two requirements. Both neighbour constraints are then satisfied with the smallest total.
The trick
- Take max(leftPass, rightPass) at each position, not the sum.
- Everyone starts with one candy.
- O(n) time, O(n) space; a slope-counting version does it in O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,0,2] Values: 1, 0, 2.
1give all 1 candy2left->right: if r[i]>r[i-1]: c[i]=c[i-1]+13right->left: if r[i]>r[i+1]: c[i]=max(c[i],c[i+1]+1)4return sum(c)Input
- array
- [1, 0, 2]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- ratings = [1, 0, 2]
- Output:
- 5
- Explanation:
- Give 2,1,2 candies → total 5.
Example 2
- Input:
- ratings = [1, 2, 2]
- Output:
- 4
- Explanation:
- 1,2,1 works → total 4.
Example 3
- Input:
- ratings = [1, 3, 2, 2, 1]
- Output:
- 7
- Explanation:
- Careful passes give total 7.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.