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
public int CandyRating(List<int> ratings) {
}Worked examples
| Call | Result |
|---|---|
CandyRating(new List<int> { 1, 2, 2 }) | 4 |
CandyRating(new List<int> { 2, 1, 2 }) | 5 |
CandyRating(new List<int> { 1, 3, 2, 2, 1 }) | 7 |
CandyRating(new List<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#
public int CandyRating(List<int> ratings) {
int n = ratings.Count;
if (n == 0) return 0;
var candies = new List<int>();
for (int i = 0; i < n; i++) candies.Add(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);
}
int total = 0;
foreach (int c in candies) total += c;
return total;
}