Problems › TypeScript › games
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
Where you start
function candyRating(ratings: number[]): number {
}Worked examples
| Call | Result |
|---|---|
candyRating([1,2,2]) | 4 |
candyRating([2,1,2]) | 5 |
candyRating([1,3,2,2,1]) | 7 |
candyRating([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 TypeScript
function candyRating(ratings: number[]): number {
const n = ratings.length;
if (n === 0) return 0;
const candies = new Array<number>(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
}
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
let total = 0;
for (const c of candies) total += c;
return total;
}