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.
candy_rating(ratings: list<int>) → int
Where you start
def candy_rating(ratings: list[int]) -> int:
Worked examples
| Call | Result |
|---|---|
candy_rating([1, 2, 2]) | 4 |
candy_rating([2, 1, 2]) | 5 |
candy_rating([1, 3, 2, 2, 1]) | 7 |
candy_rating([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 Python
def candy_rating(ratings: list[int]) -> int:
n = len(ratings)
if n == 0:
return 0
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
return sum(candies)