LeetCode Hard –  Candy

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.

Example 1:

Input: ratings = [1,0,2]

Output: 5

Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]

Output: 4

Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

Java Solution

To solve this problem, you can iterate over the array twice, first from left to right and then from right to left. In each iteration, you can update the number of candies each child should have based on their ratings and the ratings of their neighbors.

Here’s the Java solution:

public class CandyDistribution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];

        // Initialize candies to 1 for each child
        Arrays.fill(candies, 1);

        // Iterate from left to right
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Iterate from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // Calculate the total number of candies
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }

    public static void main(String[] args) {
        CandyDistribution solution = new CandyDistribution();

        // Example 1
        int[] ratings1 = {1, 0, 2};
        System.out.println(solution.candy(ratings1));  // Output: 5

        // Example 2
        int[] ratings2 = {1, 2, 2};
        System.out.println(solution.candy(ratings2));  // Output: 4
    }
}

This Java code defines a CandyDistribution class with the candy method, which calculates the minimum number of candies needed to distribute to the children based on their ratings. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for distributing candies based on children’s ratings:

class CandyDistribution:
    def candy(self, ratings):
        n = len(ratings)
        candies = [1] * n

        # Iterate from left to right
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Iterate from right to left
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        # Calculate the total number of candies
        total_candies = sum(candies)

        return total_candies

# Test cases
solution = CandyDistribution()

# Example 1
ratings1 = [1, 0, 2]
print(solution.candy(ratings1))  # Output: 5

# Example 2
ratings2 = [1, 2, 2]
print(solution.candy(ratings2))  # Output: 4

This Python code defines a CandyDistribution class with the candy method, which calculates the minimum number of candies needed to distribute to the children based on their ratings. The provided test cases demonstrate its usage.