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 * 104The #135 Candy problem requires distributing candies to children based on their ratings while satisfying two rules: each child must receive at least one candy, and children with higher ratings than their neighbors must receive more candies. The challenge is to minimize the total candies while maintaining these constraints.
A common greedy approach uses two passes through the array. First, traverse from left to right and ensure each child with a higher rating than the left neighbor gets more candies. Then perform a right-to-left pass to enforce the same rule relative to the right neighbor. During the second pass, take the max of the current assignment and the required value to maintain both constraints.
This strategy ensures all conditions are satisfied while minimizing the candy count. The approach runs in O(n) time because the array is scanned twice, and it typically uses O(n) extra space for storing intermediate candy counts.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two-pass Greedy (Left-to-Right and Right-to-Left) | O(n) | O(n) |
Techdose
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int candy(int* ratings, int ratingsSize) {
5 int candies[
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.
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.
Time Complexity: O(n)
Space Complexity: O(n)
1public class
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach uses a greedy strategy with two passes over the ratings array. The first pass ensures the left neighbor condition and the second pass enforces the right neighbor rule while taking the maximum candies required. This guarantees the minimum candies distributed while satisfying both constraints.
Yes, the Candy problem is a well-known greedy interview question that has appeared in coding interviews at major tech companies. It tests understanding of greedy strategies, array traversal, and handling local constraints efficiently.
A single pass cannot guarantee both neighbor conditions simultaneously. The left-to-right pass handles increasing sequences from the left, while the right-to-left pass corrects cases where a child must have more candies than the right neighbor.
An auxiliary array is typically used to store the number of candies assigned to each child during the greedy passes. This allows easy updates and comparisons when enforcing neighbor constraints.
This Java solution also utilizes two int arrays `left` and `right`, which store information about candy requirements for each child based on rating comparison results from either side. In this way, the optimal candy distribution sum takes maximum of both conditions.