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:
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.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104Problem Overview: You receive an array of ratings where each element represents a child's rating. Every child must get at least one candy, and children with a higher rating than their immediate neighbor must receive more candies. The goal is to minimize the total candies distributed while satisfying both constraints.
Approach 1: Two-Pass Solution (Greedy) (Time: O(n), Space: O(n))
This greedy strategy scans the ratings twice to enforce the left and right neighbor constraints independently. Start by allocating one candy to every child using an array candies. In the first pass (left → right), if ratings[i] > ratings[i-1], assign candies[i] = candies[i-1] + 1. This guarantees that higher-rated children on the right get more candies than the left neighbor. The second pass (right → left) fixes the opposite condition: if ratings[i] > ratings[i+1], update candies[i] = max(candies[i], candies[i+1] + 1). Using max preserves assignments from the first pass. Finally, sum the array to get the minimum candies. This method is simple, deterministic, and widely accepted in interviews. It’s a classic Greedy pattern applied on an Array.
Approach 2: Single-Pass with Two Arrays (Time: O(n), Space: O(n))
Another way to model the constraints is to compute two directional requirements explicitly. Maintain two arrays: left[i] represents the candies needed to satisfy the left neighbor rule, and right[i] represents the candies required to satisfy the right neighbor rule. Traverse left → right to populate left: when ratings[i] > ratings[i-1], set left[i] = left[i-1] + 1, otherwise keep it at 1. Then traverse right → left to fill right similarly using the right neighbor comparison. The final candies for each child become max(left[i], right[i]), ensuring both conditions hold simultaneously. Summing these values yields the minimum valid distribution. This approach makes the directional constraints explicit and can be easier to reason about when debugging greedy logic.
Recommended for interviews: The two-pass greedy solution is the expected answer. It demonstrates that you can break the constraint into directional rules and enforce them with linear scans. Explaining the intuition behind the passes shows understanding of greedy algorithms. Mentioning the two-array variation helps show alternative thinking, but the single array two-pass implementation is typically what interviewers want to see.
The idea behind the Two-Pass Solution is to first ensure each child has more candies than the child before them if their rating is higher, and then make another pass to ensure the condition is also satisfied going from right to left. By leveraging two passes, we ensure that the candy distribution meets the requirements in both directions.
This solution uses two passes over the ratings array.
In the first pass, we move from left to right, ensuring that each child has more candies than their left neighbor if they have a higher rating. In the second pass, we move from right to left, adjusting candies to maintain the higher-rating-more-candies constraint relative to their right neighbor. Finally, we sum up the candy totals.
Time Complexity: O(n) - where n is the number of children, because we make two linear passes through the ratings.
Space Complexity: O(n) - where n is the number of children, due to the storage of candies array.
This method involves the use of two arrays to maintain the candies given on left-to-right and right-to-left conditions separately. Instead of managing passes sequentially, we compute the required candies for each condition independently, and then derive the final candy count based on maximum requirements from both arrays at each index.
The solution employs two arrays `left` and `right` which are used to store candies count by considering the rating increase from left to right and right to left respectively. Finally, for each child, the maximum from `left` and `right` arrays is chosen as the candy count.
Time Complexity: O(n)
Space Complexity: O(n)
We initialize two arrays left and right, where left[i] represents the minimum number of candies the current child should get when the current child's score is higher than the left child's score, and right[i] represents the minimum number of candies the current child should get when the current child's score is higher than the right child's score. Initially, left[i]=1, right[i]=1.
We traverse the array from left to right once, and if the current child's score is higher than the left child's score, then left[i]=left[i-1]+1; similarly, we traverse the array from right to left once, and if the current child's score is higher than the right child's score, then right[i]=right[i+1]+1.
Finally, we traverse the array of scores once, and the minimum number of candies each child should get is the maximum of left[i] and right[i], and we add them up to get the answer.
Time complexity O(n), space complexity O(n). Where n is the length of the array of scores.
| Approach | Complexity |
|---|---|
| Two-Pass Solution | Time Complexity: O(n) - where n is the number of children, because we make two linear passes through the ratings. Space Complexity: O(n) - where n is the number of children, due to the storage of candies array. |
| Single-Pass with Two Arrays | Time Complexity: O(n) Space Complexity: O(n) |
| Two traversals | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Greedy (Single Array) | O(n) | O(n) | Best general solution. Clean logic with two directional scans enforcing neighbor constraints. |
| Single-Pass with Two Arrays | O(n) | O(n) | Useful when you want to explicitly track left and right requirements before combining them. |
L12. Candy | Slope Approach Intuition Based • take U forward • 134,960 views views
Watch 9 more video solutions →Practice Candy with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor