Candy Distribution

Problem Statement

Given ratings of children in a line, distribute candies such that each child gets at least 1 candy, and children with higher ratings get more than their neighbors. Minimize total candies. This hard-level greedy problem is about fairness—reward those standout kids!

Example

Input: ratings = [1, 0, 2]

Output: 5 (1, 1, 3)

Input: ratings = [1, 2, 2]

Output: 4 (1, 2, 1)

Code

public class Solution {
    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 total = 0;
        for (int candy : candies) total += candy;
        return total;
    }
}
            

def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
    return sum(candies)
            

function candy(ratings) {
    let n = ratings.length;
    let candies = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
    }
    for (let i = n-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) candies[i] = Math.max(candies[i], candies[i+1] + 1);
    }
    return candies.reduce((a, b) => a + b, 0);
}
            

Explanation

• Greedy Choice: Assign candies in two passes: left-to-right, then right-to-left.
• Flow: Ensure higher ratings get more than neighbors.
• Example: [1,0,2] → [1,1,1] → [1,1,3] after right pass.

Note