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
Go 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
func candyRating(ratings []int) int {
}Worked examples
| Call | Result |
|---|---|
candyRating([]int{1, 2, 2}) | 4 |
candyRating([]int{2, 1, 2}) | 5 |
candyRating([]int{1, 3, 2, 2, 1}) | 7 |
candyRating([]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 Go
func candyRating(ratings []int) int {
n := len(ratings)
if n == 0 {
return 0
}
candies := make([]int, n)
for i := range candies {
candies[i] = 1
}
for i := 1; i < n; i++ {
if ratings[i] > ratings[i-1] {
candies[i] = candies[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
candies[i] = candies[i+1] + 1
}
}
total := 0
for _, c := range candies {
total += c
}
return total
}