Assign candies to children so that each child gets at least one candy and higher-rated children than an adjacent neighbor get more candies, while minimizing the total.
Problem
You are given an array ratings where ratings[i] is the performance or preference rating of the i-th child standing in a line.
You must distribute candies to these children under the following rules:
- Every child must receive at least one candy.
- If a child has a higher rating than an immediate neighbor, that child must receive more candies than that neighbor.
Return the minimum number of candies needed to satisfy both rules.
Goal
Compute the smallest possible total number of candies that can be distributed.
Input Format
- An integer array
ratingswhereratings[i]is the rating of thei-th child.
Output Format
- Return a single integer: the minimum total number of candies required.
Constraints
1 <= ratings.length- Ratings are integers.
- The exact platform constraints are not guaranteed here; solve for the general case.
- Aim for linear time and linear or constant extra space.
Example 1
Input
ratings = [1,0,2]
Output
5
Explanation
A minimum valid distribution is [2,1,2], which totals 5 candies.
Example 2
Input
ratings = [1,2,2]
Output
4
Explanation
A minimum valid distribution is [1,2,1], which totals 4 candies.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.