135. Candy
hardDistribute the minimum candies among children with ratings such that higher-rated neighbors get more. Two greedy sweeps — left-to-right then right-to-left — collapse a nasty constraint problem into linear time.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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: each child must have at least one candy, and children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.
Constraints
n == ratings.length1 <= n <= 2 * 10^40 <= ratings[i] <= 2 * 10^4
Examples
Example 1
ratings = [1,0,2]5Explanation: Give the children 2, 1, 2 candies respectively.
Example 2
ratings = [1,2,2]4Explanation: Give the children 1, 2, 1 candies. The third child gets 1 candy because their rating is not strictly greater than their neighbor's.
Example 3
ratings = [1,3,4,5,2]11Explanation: Give 1, 2, 3, 4, 1 candies — the descent from 5 down to 2 needs special handling.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Each child has two constraints: 'more than left neighbor if rated higher' and 'more than right neighbor if rated higher'. Can you satisfy them with two separate sweeps?
Hint 2
Left-to-right pass: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1. Otherwise set candies[i] = 1.
Hint 3
Right-to-left pass: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1). Sum the array.
Solution approach
Reveal approach
Two-pass greedy. Initialize a candies array of length n filled with 1 (every child gets at least one). Left-to-right pass: for i from 1 to n-1, if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1. This satisfies the left-neighbor constraint everywhere. Right-to-left pass: for i from n-2 down to 0, if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1). Taking the max preserves any larger value the left pass already assigned, which is crucial for peaks like [1,3,4,5,2] where the 5 must be larger than both neighbors. Sum the candies array for the answer. Each pass is O(n) and we use O(n) extra space (which can be reduced to O(1) by simulating the right pass with running counters, but the two-array version is far easier to get right under interview pressure).
Complexity
- Time
- O(n)
- Space
- O(n)
Related patterns
- greedy
- two-pass
Related problems
- 134. Gas Station
- 42. Trapping Rain Water
- 45. Jump Game II
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Apple
- Meta
Practice these live with InterviewChamp.AI
Drill Candy and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →