Candy Distribution

Share

Children in a line get ratings. Each child must have at least 1 candy, higher-rated child gets more than neighbor. Minimize candies.

Example 1
Input: ratings=[1,0,2] → Output: 5. Distribute [2,1,2].
Example 2
Input: ratings=[1,2,2] → Output: 4. Distribute [1,2,1].

Solution Approach

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
Java
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)