Problem Description

The Candy problem from LeetCode is as follows:

There are n children standing in a line. Each child is assigned a rating value given in an integer array ratings, where ratings[i] represents the rating of the i-th child.

You are to distribute candies to these children following two rules:

• Each child must have at least one candy.
• Children with a higher rating than their immediate neighbor(s) must get more candies than those neighbors.

Find and return the minimum number of candies required to distribute to all the children.

Constraints:

• 1 ≤ n ≤ 2 × 10⁴
• ratings[i] is an integer
• There is always at least one valid way to distribute candies

Thought Process

At first glance, distributing candies based on the ratings might seem to require checking every possible way to assign candies, but that quickly becomes infeasible as n grows.

The brute-force approach would be to try all possible distributions that satisfy the rules, but this is extremely inefficient. Instead, let's look for patterns and optimizations:

• Every child must get at least one candy, so start with one candy for each child.
• For any child with a higher rating than their neighbor, they must get more candies than that neighbor.

If we process the array from left to right, we can ensure that each child has more candies than their left neighbor if their rating is higher. But this doesn't guarantee the right neighbor constraint. So, we need a way to process both left and right neighbor relationships.

This leads to the idea of making two passes: one left-to-right and one right-to-left, adjusting candies accordingly.

Solution Approach

To solve the problem efficiently, we follow these steps:

1. Initialization:
   • Create a candies array of the same length as ratings, initializing all values to 1 (since each child must get at least one candy).
2. Left-to-Right Pass:
   • Iterate from left to right (from the second child to the last).
   • If the current child's rating is higher than the left neighbor, give them one more candy than the left neighbor.
3. Right-to-Left Pass:
   • Iterate from right to left (from the second last child to the first).
   • If the current child's rating is higher than the right neighbor, ensure they have at least one more candy than the right neighbor. Set candies[i] = max(candies[i], candies[i+1] + 1) to preserve any previous increases from the left-to-right pass.
4. Summing Up:
   • Add up all the values in the candies array to get the minimum total candies needed.

This approach ensures that both neighbor constraints are satisfied for every child.

Example Walkthrough

Let's take an example: ratings = [1, 0, 2]

1. Initialization:
   candies = [1, 1, 1]
2. Left-to-Right Pass:
   • i = 1: ratings[1] (0) < ratings[0] (1) → no change
   • i = 2: ratings[2] (2) > ratings[1] (0) → candies[2] = candies[1] + 1 = 2
   candies = [1, 1, 2]
3. Right-to-Left Pass:
   • i = 1: ratings[1] (0) > ratings[2] (2) → no change
   • i = 0: ratings[0] (1) > ratings[1] (0) → candies[0] = max(1, 1 + 1) = 2
   candies = [2, 1, 2]
4. Sum: 2 + 1 + 2 = 5

The minimum number of candies required is 5.

Time and Space Complexity

Brute-Force Approach:

• Would require checking every possible distribution, which is exponential in time and not feasible for large n.

• Time Complexity: O(n) — We make two passes over the array and sum the result, each requiring O(n) time.
• Space Complexity: O(n) — We use an extra array of size n to store the candies for each child.

The optimized approach is efficient and suitable for large input sizes.

Summary

The Candy problem requires distributing candies so that each child gets at least one, and children with higher ratings than their immediate neighbors get more candies. By initializing all candies to one, then making two passes (left-to-right and right-to-left) to enforce the constraints, we can efficiently find the minimum total candies needed. The two-pass algorithm is both simple and elegant, ensuring all rules are satisfied with optimal time and space efficiency.

Code Implementation

class Solution:
    def candy(self, ratings):
        n = len(ratings)
        candies = [1] * n
        
        # Left to right pass
        for i in range(1, n):
            if ratings[i] > ratings[i-1]:
                candies[i] = candies[i-1] + 1
        
        # Right to left pass
        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)
      

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);
        
        // Left to right pass
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1])
                candies[i] = candies[i - 1] + 1;
        }
        
        // Right to left pass
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1])
                candies[i] = max(candies[i], candies[i + 1] + 1);
        }
        
        int total = 0;
        for (int c : candies) total += c;
        return total;
    }
};
      

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

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

        // 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);
            }
        }

        int total = 0;
        for (int c : candies) total += c;
        return total;
    }
}
      

var candy = function(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);

    // Left to right pass
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // Right to left pass
    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);
};