Children in a line get ratings. Each child must have at least 1 candy, higher-rated child gets more than neighbor. Minimize candies.
Input: ratings=[1,0,2] → Output: 5. Distribute [2,1,2].
Input: ratings=[1,2,2] → Output: 4. Distribute [1,2,1].
Two pass greedy: left-to-right ensure ascending satisfied, right-to-left ensure descending satisfied.
- Initialize candies array with all 1s
- Left pass: if ratings[i]>ratings[i-1] candies[i]=candies[i-1]+1
- Right pass: if ratings[i]>ratings[i+1] candies[i]=max(candies[i],candies[i+1]+1)
- Sum all candies
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
for (int i = n-2; i >= 0; i--)
if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1]+1);
int sum = 0;
for (int c : candies) sum += c;
return sum;
}
- Time Complexity: O(n)
- Space Complexity: O(n)