Watch 10 video solutions for Candy, a hard level problem involving Array, Greedy. This walkthrough by Techdose has 98,690 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |