Skip to content

135. 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

Solution:

Identify the Constraints:

"Each child must have at least one candy.", "Children with a higher rating get more candies than their neighbors.", These constraints make it challenging to adjust candies directly for each child, as increasing candies for one child could lead to violations in neighboring conditions.

Intuitive Greedy Strategy:

For such problems, a greedy approach often works well. We can ensure that each child meets the conditions by doing two passes: one from left to right and another from right to left.

The core of the greedy approach here is to focus on local conditions for each child and its neighbors, without revisiting or readjusting already valiated children.

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

        // Step 1: Give each child at least 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: Sum up all the candies
        int totalCandies = 0;
        for (int candy : candies){
            totalCandies = candy + totalCandies;
        }

        return totalCandies;
    }
}

// TC: O(n)
// SC: O(n)