Candy

135.Candy

Array

Greedy

Math

Problem Statement:

There are n children standing in a line. Each child is assigned a rating value given in an integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy, and children with a higher rating get more candies than their neighbors.

Example:

Input:

ratings = [1,0,2]

→

Output:

5

Algorithm:

1. Two pass approach: left to right and right to left
2. First pass ensures right neighbor rule
3. Second pass ensures left neighbor rule
4. Take maximum at each position

Complexity:

Time: O(n) | Space: O(n) for array solution, O(1) for optimized

Java Solution:

public int candy(int[] ratings) {
    int[] candies = new int[ratings.length];
    Arrays.fill(candies, 1);  // Initialize with one candy each
    
    // Forward pass to handle right neighbor
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    
    int sum = candies[ratings.length - 1];
    // Backward pass to handle left neighbor
    for (int i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
        sum += candies[i];
    }
    return sum;
}

// Optimized O(1) space solution using peak-valley approach
public int candyNoExtraSpace(int[] ratings) {
    if (ratings.length <= 1) return ratings.length;
    
    int candies = 0;
    int up = 0, down = 0;
    int oldSlope = 0;
    
    for (int i = 1; i < ratings.length; i++) {
        int newSlope = (ratings[i] > ratings[i - 1]) ? 1 
            : (ratings[i] < ratings[i - 1] ? -1 : 0);

        if ((oldSlope > 0 && newSlope == 0) || 
            (oldSlope < 0 && newSlope >= 0)) {
            candies += count(up) + count(down) + Math.max(up, down);
            up = 0;
            down = 0;
        }
        
        if (newSlope > 0) up++;
        else if (newSlope < 0) down++;
        else candies++;

        oldSlope = newSlope;
    }
    candies += count(up) + count(down) + Math.max(up, down) + 1;
    return candies;
}

private int count(int n) {
    return (n * (n + 1)) / 2;
}

Python Solution:

def candy(self, ratings: List[int]) -> int:
    n = len(ratings)
    candies = [1] * n
    
    # Forward pass
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
            
    # Backward pass
    total = candies[-1]
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
        total += candies[i]
        
    return total

C++ Solution:

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