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 are given an array of ratings where each index represents a child. Every child must receive at least one candy, and children with higher ratings than their immediate neighbors must receive more candies. The goal is to minimize the total number of candies distributed while satisfying both rules.
Approach 1: Two-Pass Greedy with One Array (O(n) time, O(n) space)
This problem is naturally solved with a greedy strategy. Start by assigning every child one candy. Then iterate from left to right: if ratings[i] > ratings[i-1], increase the candy count for i to candies[i-1] + 1. This ensures the left neighbor rule is satisfied. After that, perform a second pass from right to left. If ratings[i] > ratings[i+1], update candies[i] to max(candies[i], candies[i+1] + 1). The max keeps both constraints valid. This two-direction sweep guarantees that every local ordering constraint is satisfied with the minimal number of candies. The algorithm runs in O(n) time and uses O(n) extra space for the candy array.
Approach 2: Single-Pass with Two Arrays (O(n) time, O(n) space)
Another way to think about the constraints is to track increasing sequences from both directions. Maintain two arrays: left[i] stores candies required when comparing each child with the left neighbor, and right[i] stores candies required when comparing with the right neighbor. Iterate left to right to fill left: if ratings[i] > ratings[i-1], set left[i] = left[i-1] + 1, otherwise keep it at 1. Then iterate right to left to fill right using the same rule with ratings[i] > ratings[i+1]. The final candy count for each child is max(left[i], right[i]). Summing these values produces the minimum valid distribution. This approach also runs in O(n) time with O(n) space and clearly separates the two directional constraints. The problem heavily relies on reasoning about local ordering in an array and applying greedy updates.
Recommended for interviews: The two-pass greedy solution is what most interviewers expect. It demonstrates that you recognized the bidirectional dependency between neighbors and resolved it with two linear scans. Explaining why one pass is insufficient, then fixing it with a reverse pass, shows strong problem-solving skills and clear understanding of greedy constraints.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
| 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) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Greedy with One Array | O(n) | O(n) | Standard interview solution that handles both neighbor constraints with minimal logic |
| Single-Pass Concept with Left/Right Arrays | O(n) | O(n) | Useful for clearly separating left and right constraints when reasoning about the problem |
Candy distribution problem • Techdose • 98,690 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