135. Candy


Problem Description

In this LeetCode problem, we are tasked with distributing candies to children in a line based on their ratings. Each child in the line has a rating value, and our goal is to allocate candies following two rules:

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

We are required to determine the minimum number of candies that we need to distribute to satisfy the above rules.

Intuition

To solve this problem, we can consider the two rules that govern how we should distribute candies. The first rule is straightforward: we can start by giving each child one candy. The second rule requires a bit more thought because we need to ensure that each child with a higher rating than their neighbor receives more candies.

One approach is to evaluate how each child compares to their neighbors from both the left and right sides separately, using two arrays, left and right. Here’s our process for arriving at the solution:

  1. We create two arrays, left and right, with the same length as the ratings array, and initialize all elements to 1, which accounts for the first rule that every child receives at least one candy.
  2. We scan through the ratings array from left to right, comparing each child's rating to their previous neighbor. If a child's rating is higher than that of the previous child, we increment the value in the corresponding left array to one plus the value for the previous child.
  3. Next, we'll need to consider the right neighbors, too. We scan through the ratings array from right to left this time. If we find that a child's rating is higher than that of the next child, we increment the right array's corresponding value to one plus the value for the next child.
  4. We then take the maximum value between the corresponding elements in left and right for each child. This step ensures that the requirements for both neighbors are satisfied.
  5. Lastly, we sum up the maximum values that we've obtained for each child, giving us the minimum number of candies needed to distribute to all the children while meeting the rules.

This algorithm effectively caters to all the possible scenarios and ensures that each child gets the correct number of candies based on their ratings and allows us to calculate the minimum total number of candies required.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which two pointer technique does Quick Sort use?

Solution Approach

The solution can be broken down into a few steps using simple algorithms and data structures pattern:

  1. Initial Setup: Two arrays named left and right of the same length as ratings are created. Both are filled with 1s, which ensures that each child gets at least one candy, adhering to the first rule.

  2. Left-to-Right Pass: Starting from the second child (at index 1), we iterate over the ratings array. If we find that the current child has a higher rating than the one to the left (at index i-1), we give the current child more candies than the left one by incrementing the left[i] value to left[i-1] + 1.

    1for i in range(1, len(ratings)):
    2    if ratings[i] > ratings[i - 1]:
    3        left[i] = left[i - 1] + 1
  3. Right-to-Left Pass: In the next step, we start from the second-to-last child and go back to the first child. Similar to the left-to-right pass, if the current child has a higher rating than the one to the right (at index i+1), we perform a similar increment on the right[i].

    1for i in range(len(ratings) - 2, -1, -1):
    2    if ratings[i] > ratings[i + 1]:
    3        right[i] = right[i + 1] + 1
  4. Combining Results: Now that we have gone through the ratings and considered each child in comparison to their left and right neighbors, we need to combine results. The final candy count for each child should be the maximum value out of left[i] and right[i]. This is because a child's final candy count must satisfy both its left and right neighbors.

    1total_candies = sum(max(left[i], right[i]) for i in range(len(ratings)))
  5. Final Result: The sum of the maximum of the left and right values for each child gives us the minimum number of candies we need to distribute.

By using two arrays, we are applying a form of Dynamic Programming where we store intermediate results ("the number of candies needed considering the left or right neighbor") to solve overlapping subproblems ("the number of candies a child should get"). The solution is efficient both in terms of time and space complexity and ensures that we adhere to the problem constraints while obtaining the correct minimum total of candies.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above.

Consider the ratings array [1, 0, 2]. We need to distribute candies to the children in such a way that all conditions are met.

  1. Initial Setup: We initialize the left and right arrays to [1, 1, 1] because each child must get at least one candy according to the first rule.

  2. Left-to-Right Pass: We iterate through the ratings array starting from the second element. Comparing each element with its left neighbor:

    • For the second child (rating 0), since 0 < 1, we do not change left[1].
    • For the third child (rating 2), since 2 > 0, we increment left[2] to left[1] + 1, so left becomes [1, 1, 2].
  3. Right-to-Left Pass: We iterate from right to left, starting from the second-to-last element:

    • For the second child (rating 0), since 0 < 2, we increment right[1] to right[2] + 1, so right becomes [1, 2, 1].
    • For the first child (rating 1), since 1 > 0, no change is needed as right[0] is already greater than right[1].
  4. Combining Results: We take the maximum value for each index between left and right.

    • The combined array will be max([1,1],[1,2]), max([1,2],[1,1]), max([2,1],[2,1]), which results in [1, 2, 2].
  5. Final Result: We sum up the values of the combined array: 1 + 2 + 2 = 5. Therefore, we need a minimum of 5 candies to distribute to the children following the rules.

By following this step-by-step process for each child's rating, we can satisfy both conditions and compute the minimum number of candies required, which in this example is 5.

Not Sure What to Study? Take the 2-min Quiz:

Which of these properties could exist for a graph but not a tree?

Python Solution

1from typing import List
2
3class Solution:
4    def candy(self, ratings: List[int]) -> int:
5        # Length of the ratings list
6        num_children = len(ratings)
7      
8        # Initialize lists to represent the minimum candies for each child from left and right perspectives
9        candies_from_left = [1] * num_children
10        candies_from_right = [1] * num_children
11      
12        # Calculate the minimum candies required from the left perspective
13        for i in range(1, num_children):
14            # If the current child has a higher rating than the previous child, 
15            # give one more candy than the previous child
16            if ratings[i] > ratings[i - 1]:
17                candies_from_left[i] = candies_from_left[i - 1] + 1
18      
19        # Calculate the minimum candies required from the right perspective
20        for i in range(num_children - 2, -1, -1):
21            # If the current child has a higher rating than the next child,
22            # give one more candy than the next child
23            if ratings[i] > ratings[i + 1]:
24                candies_from_right[i] = candies_from_right[i + 1] + 1
25      
26        # Sum the max number of candies required from both perspectives for each child
27        # to ensure all conditions are met
28        total_candies = sum(max(candies_left, candies_right) for candies_left, candies_right in zip(candies_from_left, candies_from_right))
29      
30        return total_candies
31

Java Solution

1class Solution {
2    public int candy(int[] ratings) {
3        int n = ratings.length; // Total number of children
4        int increasingCount = 0; // Counter for increasing ratings
5        int decreasingCount = 0; // Counter for decreasing ratings
6        int peakCandy = 0; // Number of candies at the peak (highest point in the current iteration)
7        int totalCandies = 1; // Start with one candy for the first child
8      
9        // Iterate through each child starting from the second one
10        for (int i = 1; i < n; i++) {
11            if (ratings[i - 1] < ratings[i]) {
12                // Rating is higher than the previous child's rating
13                increasingCount++;
14                peakCandy = increasingCount + 1; // The current child gets one more candy than the increasing count
15                decreasingCount = 0; // Reset decreasing count
16                totalCandies += peakCandy; // Update total candies with the current child's candies
17            } else if (ratings[i] == ratings[i - 1]) {
18                // Rating is equal to the previous child's rating
19                // Reset the peak, increasing count, and decreasing count
20                peakCandy = 0;
21                increasingCount = 0;
22                decreasingCount = 0;
23                totalCandies++; // Each child gets at least one candy
24            } else {
25                // Rating is lower than the previous child's rating
26                decreasingCount++;
27                increasingCount = 0; // Reset increasing count
28                // Add the number of candies for decreasing sequence.
29                // If peak candy count is not enough to cover the decreasing sequence, an extra candy is given to the peak
30                totalCandies += decreasingCount + (peakCandy > decreasingCount ? 0 : 1);
31            }
32        }
33      
34        // Return the computed total number of candies needed
35        return totalCandies;
36    }
37}
38

C++ Solution

1#include <vector>
2#include <algorithm> // Included to use std::max
3
4class Solution {
5public:
6    /**
7     * Calculate the minimum number of candies to distribute to children,
8     * given different ratings, where each child must have at least one candy,
9     * and children with a higher rating than their neighbors must have more candies.
10     * 
11     * @param ratings A vector of integers where each element represents the rating of a child.
12     * @return The minimum number of candies required.
13     */
14    int candy(vector<int>& ratings) {
15        // Get the number of children
16        int numChildren = ratings.size();
17  
18        // Initialize left and right vectors with 1 candy for each child
19        vector<int> candiesFromLeft(numChildren, 1);
20        vector<int> candiesFromRight(numChildren, 1);
21  
22        // Distribute candies from left to right, ensuring each child with a higher rating
23        // than the left neighbor gets more candies
24        for (int i = 1; i < numChildren; ++i) {
25            if (ratings[i] > ratings[i - 1]) {
26                candiesFromLeft[i] = candiesFromLeft[i - 1] + 1;
27            }
28        }
29  
30        // Distribute candies from right to left with the same logic
31        for (int i = numChildren - 2; i >= 0; --i) {
32            if (ratings[i] > ratings[i + 1]) {
33                candiesFromRight[i] = candiesFromRight[i + 1] + 1;
34            }
35        }
36  
37        // Calculate the total amount of candies by taking the maximum of
38        // candies from left and right at each position
39        int totalCandies = 0;
40        for (int i = 0; i < numChildren; ++i) {
41            totalCandies += std::max(candiesFromLeft[i], candiesFromRight[i]);
42        }
43  
44        // Return the total number of candies needed
45        return totalCandies;
46    }
47};
48

Typescript Solution

1function candy(ratings: number[]): number {
2    const numChildren = ratings.length;
3    const candiesFromLeft = new Array(numChildren).fill(1);
4    const candiesFromRight = new Array(numChildren).fill(1);
5
6    // Traverse from left to right, and assign candies ensuring that each child
7    // with a higher rating than the left neighbor receives more candies
8    for (let i = 1; i < numChildren; ++i) {
9        if (ratings[i] > ratings[i - 1]) {
10            candiesFromLeft[i] = candiesFromLeft[i - 1] + 1;
11        }
12    }
13
14    // Traverse from right to left, and assign candies ensuring that each child
15    // with a higher rating than the right neighbor receives more candies
16    for (let i = numChildren - 2; i >= 0; --i) {
17        if (ratings[i] > ratings[i + 1]) {
18            candiesFromRight[i] = candiesFromRight[i + 1] + 1;
19        }
20    }
21
22    // Calculate the minimum required candies by selecting the maximum number
23    // of candies assigned from either direction for each child
24    let totalCandies = 0;
25    for (let i = 0; i < numChildren; ++i) {
26        totalCandies += Math.max(candiesFromLeft[i], candiesFromRight[i]);
27    }
28
29    // Return the total number of candies needed
30    return totalCandies;
31}
32
Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The time complexity of the code is O(n). Here's the analysis:

  • There are two single-pass for-loops that go through the list of ratings which contains n elements. Each loop runs in O(n) and they are run sequentially, not nested. So the time complexity remains O(n).
  • The final return statement uses a generator expression with zip to combine the two lists (left and right) and sum the maximum values of corresponding elements. zip function pairs up the elements of both lists, which takes O(n) time, and the summation also takes O(n) time since each element is considered once.

Combining these linear operations still results in a total time complexity of O(n).

The space complexity of the code is O(n). This is due to:

  • Two additional lists left and right, each of size n, are created to store the incrementing sequences based on the ratings.
  • No other additional space that scales with the input size is used, so the total space complexity is the sum of the space used by these two lists, which is 2 * O(n) simplified to O(n) as constants are dropped in big O notation.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫