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
The 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. This two-pass greedy approach guarantees all local constraints are met with minimal candies.
Optimal Approach
Initialize an array with 1 candy per child. Traverse left to right, incrementing candies when the current rating is higher than the previous. Then traverse right to left, updating candies to the max of current and one more than the right neighbor if the current rating is higher. Summing the final candies array yields the minimum total.
Time
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
| 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) |
| 15 | return sum(candies) |
Objective
To adjust candies to satisfy the right neighbor constraint and compute the total minimum candies required.
Key Insight
The right-to-left pass ensures that children with higher ratings than their right neighbors have more candies, correcting any violations from the first pass. Using max preserves previously assigned candies if they already satisfy the constraint. Summing the final candies array yields the minimal total satisfying all constraints.
Interview Quick-Check
Core Logic
Traverse from right to left, updating candies[i] to max(candies[i], candies[i+1] + 1) if ratings[i] > ratings[i+1], enforcing right neighbor constraints without violating left neighbor assignments.
State & Boundaries
Start from the second last index and move backward to index 0 to cover all children with right neighbors.
Complexity
Summing the candies array at the end is O(n), maintaining overall linear time complexity.
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.
candies = [1] * nInitialize candies array with 1 candy per child.
Assigning one candy to each child satisfies the minimum candy requirement and provides a baseline for further increments.
return sum(candies)Return the sum of all candies assigned.
Summing the candies array yields the minimum total candies required to satisfy all constraints, which is the problem's final output.
if ratings[i] > ratings[i-1]:Check if current child's rating is higher than the previous child's.
This condition identifies when the current child must receive more candies than the left neighbor to satisfy the problem's constraints.
if ratings[i] > ratings[i+1]:Check if current child's rating is higher than the next child's.
This condition detects when the current child must have more candies than the right neighbor to satisfy the problem's constraints.
for i in range(1, n):Iterate from the second child to the end.
Starting from index 1 allows comparison with the previous child to enforce the left neighbor rating constraint.
for i in range(n-2, -1, -1):Iterate backward from the second last child to the first.
This reverse iteration allows enforcing the right neighbor constraint by comparing each child with the one to its right.
n = len(ratings)Calculate the number of children.
Knowing the length of the ratings array is essential for iterating through children and initializing the candies array correctly.
Test Your Understanding
Why are two passes (left-to-right and right-to-left) necessary to correctly assign candies?
Because a single pass only enforces the constraint in one direction, potentially violating it in the other. The two passes ensure that both left and right neighbor constraints are satisfied, guaranteeing a globally valid minimal candy distribution.
Related Problems
Greedy 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