Candy Distribution – LeetCode Problems: A Complete Series

Problem Statement:

You have N children standing in a line, and each child has an associated rating value. You need to distribute candies to these children based on the following requirements:

1. Each child must receive at least one candy.
2. Children with a higher rating than their immediate neighbors must receive more candies than those neighbors.

Your task is to determine the minimum number of candies required to satisfy these conditions.

Example:

Input: ratings = [1, 0, 2]
Output: 5
Explanation: You can distribute candies as follows: [2, 1, 2]. 
The child with rating `1` gets `2` candies, the child with rating `0` gets `1` candy, 
and the child with rating `2` gets `2` candies, resulting in a total of `5` candies.

Input: ratings = [1, 2, 2]
Output: 4
Explanation: You can distribute candies as follows: [1, 2, 1]. 
The first child gets `1` candy, the second child gets `2` candies (because they have a higher rating than the first), 
and the third child gets `1` candy (because their rating is equal to the second child).

Input:

• An integer array ratings of length N (where 1 <= N <= 10^4), representing the rating of each child.

Output:

• An integer representing the minimum number of candies required.

Approach to the Problem:

To solve this problem, we can use a two-pass approach:

1. Left to Right Pass: Traverse the ratings from left to right, ensuring that each child with a higher rating than the previous child gets more candies.
2. Right to Left Pass: Traverse the ratings from right to left, ensuring that each child with a higher rating than the next child also gets more candies.

After these two passes, the total number of candies will be the sum of the candies distributed to each child.

Code Implementation:

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

        // Step 1: Initialize each child with 1 candy
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }

        // Step 2: Left to Right Pass
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Step 3: Right to Left Pass
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // Step 4: Calculate total candies
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }
}

Step-by-Step Explanation:

1. Initialization (Lines 4-7):

int n = ratings.length;
int[] candies = new int[n];

// Step 1: Initialize each child with 1 candy
for (int i = 0; i < n; i++) {
    candies[i] = 1;
}

• We initialize an array candies of the same length as ratings to track the number of candies each child receives.
• Initially, each child receives 1 candy.

2. Left to Right Pass (Lines 9-14):

for (int i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
        candies[i] = candies[i - 1] + 1;
    }
}

• We iterate from the second child to the last child.
• If a child’s rating is greater than the previous child’s rating, we give them more candies than the previous child.

3. Right to Left Pass (Lines 16-21):

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

• We iterate from the second last child to the first child.
• If a child’s rating is greater than the next child’s rating, we update their candies to ensure they have more than the next child, taking the maximum to satisfy both passes.

4. Calculate Total Candies (Lines 23-27):

int totalCandies = 0;
for (int candy : candies) {
    totalCandies += candy;
}

• We sum up the total number of candies distributed to all children.

Time and Space Complexity:

• Time Complexity: O(N), where N is the number of children. We make two passes over the ratings array.
• Space Complexity: O(N), for the candies array that holds the number of candies for each child.

Example Execution:

Let’s take the input:

Input: ratings = [1, 0, 2]

Execution Steps:

1. Initialization:

• candies = [1, 1, 1]

1. Left to Right Pass:

• For child 1 (rating 0), no change: candies = [1, 1, 1]
• For child 2 (rating 2), increase to 2: candies = [1, 1, 2]

1. Right to Left Pass:

• For child 1 (rating 0), no change: candies = [1, 1, 2]
• For child 0 (rating 1), increase to 2: candies = [2, 1, 2]

1. Total Candies Calculation:

• totalCandies = 2 + 1 + 2 = 5

Output:

Output: 5  // Minimum candies required to satisfy the conditions.

For any further help or modifications, feel free to reach out to Divi Tech HR Solution (info@divisolutions.in). Don’t forget to like and comment on this blog to share your feedback and support! Keep practicing these highly-rated LeetCode problems for interview preparation!