Candy
Problem
Given an integer array ratings representing the ratings of children standing in a line, return the minimum number of candies you must distribute such that each child has at least one candy and children with a higher rating than their immediate neighbors receive more candies than those neighbors.
- 1 ≤ ratings.length ≤ 2 * 10⁴
- 0 ≤ ratings[i] ≤ 2 * 10⁴
Example
ratings = [1, 0, 2]5Start by giving each child 1 candy: [1,1,1]. The child at index 1 has rating 0, less than index 0, so no change. The child at index 2 has rating 2, higher than index 1, so candies at index 2 must be more than index 1. Update candies to [2,1,2]. The total is 5. The critical moment is the two-pass approach: first scanning left to right to ensure increasing sequences get more candies, then right to left to fix decreasing sequences, ensuring all constraints are met.
Approach
Straightforward Solution
A brute-force approach might repeatedly adjust candies until all constraints are satisfied, potentially leading to O(n^2) time due to repeated passes and updates.
Core Observation
The problem requires a local ordering constraint: if a child's rating is higher than a neighbor's, that child must have more candies. This creates a partial order that must be respected in both directions along the line.
Path to Optimal
PreviewThe key insight is to perform two linear passes: one from left to right to ensure each child has more candies than the left neighbor if their rating is higher, and one from right to left to ensure the same for the right neighbor…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize an array with 1 candy per child. Traverse left to right, incrementing candies when the current rating is higher than the previous…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each pass (left-to-right and right-to-left) iterates through the ratings array once, resulting in linear time complexity.
Space
O(n)
An auxiliary array of size n is used to store candy counts for each child, which scales linearly with input size.
Pattern Spotlight
Greedy Algorithms (Two Pass Local Constraint Enforcement)
When local ordering constraints exist in a linear structure, a two pass greedy approach that scans forward and backward can efficiently enforce all constraints by propagating the minimal necessary increments in each direction.
Solution
| 1 | class Solution: |
| 2 | def candy(self, ratings: List[int]) -> int: |
| 3 | |
| 4 | n = len(ratings) |
| 5 | candies = [1] * n |
| 6 | |
| 7 | for i in range(1, n): |
| 8 | if ratings[i] > ratings[i-1]: |
| 9 | candies[i] = candies[i-1] + 1 |
| 10 | |
| 11 | for i in range(n-2, -1, -1): |
| 12 | if ratings[i] > ratings[i+1]: |
| 13 | candies[i] = max(candies[i], candies[i+1] + 1) |
| 14 | |
| 15 | return sum(candies) |
Step-by-Step Solution
Assign Initial Candies and Enforce Left Neighbor Constraint
| 4 | n = len(ratings) |
| 5 | candies = [1] * n |
| 7 | for i in range(1, n): |
| 8 | if ratings[i] > ratings[i-1]: |
| 9 | candies[i] = candies[i-1] + 1 |
Objective
To initialize candies and ensure each child has more candies than the left neighbor if their rating is higher.
Key Insight
Starting with one candy per child satisfies the minimum requirement. The left-to-right pass enforces the increasing rating constraint by incrementing candies only when the current rating exceeds the previous one. This pass guarantees local correctness from left neighbors but does not yet consider right neighbors.
Interview Quick-Check
Core Logic
Initialize candies with 1 each, then scan left to right, increasing candies[i] to candies[i-1] + 1 if ratings[i] > ratings[i-1], ensuring left neighbor constraints.
State & Boundaries
Start from index 1 because the first child has no left neighbor.
Common Pitfalls & Bugs
Failing to initialize candies to 1 for all children can lead to invalid zero or missing candy assignments.
Enforce Right Neighbor Constraint and Aggregate Result
To adjust candies to satisfy the right neighbor constraint and compute the total minimum candies required.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
candies[i] = candies[i-1] + 1Assign candies to current child as one more than the previous child's candies.
This line is the core of the left-to-right greedy enforcement, ensuring that any child with a higher rating than the left neighbor receives strictly more candies, which is necessary for correctness.
candies[i] = max(candies[i], candies[i+1] + 1)Update candies for current child to the maximum of its current candies and one more than the right neighbor's candies.
This line is critical because it reconciles the two directional constraints by taking the maximum, ensuring no constraint is violated while minimizing candy distribution.
Full line-by-line criticality + rationale for all 9 lines available on Pro.
Test Your Understanding
Why are two passes (left-to-right and right-to-left) necessary to correctly assign candies?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Candy from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Candy drill