Solution Explanation for LeetCode 135: Candy

This problem asks for the minimum number of candies to distribute to children, such that each child gets at least one candy, and children with higher ratings get more candies than their neighbors. The most efficient solution involves two passes through the ratings array.

Approach:

The core idea is that we need to consider the candy distribution from both the left and the right. A child might need more candies based on their neighbors on either side.

1. Left Pass: We iterate through the ratings array from left to right. We maintain a left array, where left[i] stores the minimum number of candies the i-th child needs considering only its left neighbor. We initialize all values in left to 1 (at least one candy). If the current child's rating is higher than its left neighbor's rating (ratings[i] > ratings[i-1]), then it needs one more candy than its left neighbor, so left[i] = left[i-1] + 1.

2. Right Pass: We perform a similar iteration from right to left, maintaining a right array. right[i] represents the minimum number of candies the i-th child needs considering only its right neighbor. The logic is the same as in the left pass, but we update right[i] based on right[i+1].

3. Combine and Sum: Finally, for each child, we take the maximum of left[i] and right[i] to ensure the condition that a higher-rated child gets more candies than its neighbors (on either side). We sum up these maximum values to get the total minimum number of candies needed.

Time and Space Complexity:

• Time Complexity: O(n) - We perform three linear passes through the array of length n.
• Space Complexity: O(n) - We use two extra arrays, left and right, each of size n.

Code Implementation (Python):

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [1] * n
        right = [1] * n
 
        # Left Pass
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
 
        # Right Pass
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right[i] = right[i + 1] + 1
 
        # Combine and Sum
        total_candies = sum(max(left[i], right[i]) for i in range(n))
        return total_candies

Code Implementation (Java):

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
 
        // Left Pass
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
 
        // Right Pass
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
 
        // Combine and Sum
        int totalCandies = 0;
        for (int i = 0; i < n; i++) {
            totalCandies += Math.max(left[i], right[i]);
        }
        return totalCandies;
    }
}

The other languages (C++, Go, TypeScript, C#) follow a very similar structure, adapting the syntax and standard library functions accordingly. The core algorithm remains the same, ensuring optimal time and space complexity.