Distribute candies by rating
Children stand in a line, each with a rating. Every child must get at least one candy, and a child with a strictly higher rating than a neighbour must get strictly more candies than that neighbour.
- Every child receives at least one candy.
- If a child has a higher rating than an immediate neighbour, the child gets more candies than that neighbour.
- Find the minimum total candies needed.
candyRating(ratings: list<int>) → int
Java needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int candyRating(List<Integer> ratings) {
}Worked examples
| Call | Result |
|---|---|
candyRating(Main.<Integer>ls(1, 2, 2)) | 4 |
candyRating(Main.<Integer>ls(2, 1, 2)) | 5 |
candyRating(Main.<Integer>ls(1, 3, 2, 2, 1)) | 7 |
candyRating(Main.<Integer>ls(3, 2, 1)) | 6 |
Hint
Two passes: left-to-right to handle increases from the left, then right-to-left to handle increases from the right.
Reference solution in Java
int candyRating(List<Integer> ratings) {
int n = ratings.size();
if (n == 0) return 0;
List<Integer> candies = new ArrayList<>();
for (int i = 0; i < n; i++) candies.add(1);
for (int i = 1; i < n; i++) {
if (ratings.get(i) > ratings.get(i - 1)) candies.set(i, candies.get(i - 1) + 1);
}
for (int i = n - 2; i >= 0; i--) {
if (ratings.get(i) > ratings.get(i + 1)) candies.set(i, Math.max(candies.get(i), candies.get(i + 1) + 1));
}
int total = 0;
for (int c : candies) total += c;
return total;
}