#135
Candy
Hard Two passes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Children stand in a line with ratings. Each gets at least one candy, and a child with a higher rating than a neighbour must get more than that neighbour. Return the minimum total.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: fewest candies so higher-rated kids get more than their neighbours.
Why this works: one pass fixes the left neighbour rule, one pass from the right fixes the right neighbour rule (take the max).
Example: ratings [1, 0, 2]
left pass: [1, 1, 2]right pass: [2, 1, 2] → 5
✦Hints open one at a time
Handle the left-neighbour rule and the right-neighbour rule separately.
Left to right: if rating rises, give one more than the left neighbour.
Right to left: if rating rises, take the max of the current value and right neighbour + 1.
↗Approach
Two greedy passes over a candies array starting at 1. Taking the max in the second pass keeps the first rule satisfied.
</>Solution (Java)
import java.util.*;
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
for (int i = n - 2; i >= 0; i--)
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1); // keep both rules
int total = 0;
for (int c : candies) total += c;
return total;
}
}!Common mistake
Overwriting in the second pass instead of taking the max, which breaks the left rule.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Greedy
🎬 Episodes 69–73: video coming soon