Candy
The key idea
A higher rating than a neighbor must mean strictly more candies. Each child is constrained from two independent sides: its left neighbor and its right neighbor. Handle the two directions in two separate greedy passes, then take the larger requirement at each position so both constraints hold at once.
Problem
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Constraints
n == ratings.length1 <= n <= 2 * 10^40 <= ratings[i] <= 2 * 10^4
Examples
Input: ratings = [1,0,2]
Output: 5
Input: ratings = [1,2,2]
Output: 4
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Greedy problems
- Assign CookiesEASY
- Best Time to Buy and Sell Stock IIMEDIUM
- Boats to Save PeopleMEDIUM
- Can Place FlowersEASY
- Dota2 SenateMEDIUM
- Gas StationMEDIUM
- Hand of StraightsMEDIUM
- Increasing Triplet SubsequenceMEDIUM
- Jump GameMEDIUM
- Jump Game IIMEDIUM
- Lemonade ChangeEASY
- Longest Happy StringMEDIUM