Candy
Problem
Children stand in a line, each with a rating. Every child must get at least one candy, and a child with a higher rating than an adjacent neighbour must get more candy than that neighbour. Return the minimum total number of candies.
Examples
Constraints
- • 1 <= n <= 2 * 10^4
- • 0 <= ratings[i] <= 2 * 10^4
Hints & approach
Hint 1
Each child has two constraints: one from the left neighbour and one from the right.
Hint 2
Satisfy the left-neighbour rule in a left-to-right pass.
Hint 3
Then satisfy the right-neighbour rule in a right-to-left pass, keeping the larger of the two requirements.
Approachtry the hints first
Give everyone 1 candy. Sweep left to right: if ratings[i] > ratings[i - 1], set candies[i] = candies[i - 1] + 1. Sweep right to left: if ratings[i] > ratings[i + 1], set candies[i] = max(candies[i], candies[i + 1] + 1). Taking the maximum keeps the first pass's guarantee while adding the second, and each value is the smallest that meets both, so the sum is minimal.
Time O(n) · Space O(n)