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
C++ 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(std::vector<int> ratings) {
}Worked examples
| Call | Result |
|---|---|
candyRating(std::vector<int>{1, 2, 2}) | 4 |
candyRating(std::vector<int>{2, 1, 2}) | 5 |
candyRating(std::vector<int>{1, 3, 2, 2, 1}) | 7 |
candyRating(std::vector<int>{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 C++
int candyRating(std::vector<int> ratings) {
int n = (int) ratings.size();
if (n == 0) return 0;
std::vector<int> candies(n, 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] = std::max(candies[i], candies[i + 1] + 1);
}
int total = 0;
for (int c : candies) total += c;
return total;
}