296. Candy
🔗 LeetCode Problem: 135. Candy
📊 Difficulty: Hard
🏷️ Topics: Array, Greedy
Problem Statement
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.
- 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.
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.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
🌳 Visual Understanding - The Candy Problem
The Problem We're Solving:
Children in line with ratings:
Child: 0 1 2
Rating: 1 0 2
Rules:
1. Each child gets at least 1 candy
2. Higher rated child gets more candy than neighbors
Question: Minimum total candies?
One valid distribution:
Child 0: 2 candies (rating 1 > 0)
Child 1: 1 candy (rating 0, lowest)
Child 2: 2 candies (rating 2 > 0)
Total: 2 + 1 + 2 = 5 ✓
Understanding "Higher Rating Gets More Candies":
Key constraint: Compare with NEIGHBORS only!
Example: ratings = [1, 3, 2]
Child 1 (rating 3):
Left neighbor: rating 1 (3 > 1) ✓ Need more than left
Right neighbor: rating 2 (3 > 2) ✓ Need more than right
Must have more candies than BOTH neighbors!
Valid distribution:
Child 0: 1 candy
Child 1: 2 candies (more than both neighbors)
Child 2: 1 candy
Total: 1 + 2 + 1 = 4
NOT valid:
Child 0: 2 candies
Child 1: 1 candy ✗ (rating 3 > 1 but candies 1 ≤ 2)
Child 2: 1 candy
Key Observations:
1. Minimum constraint: Everyone gets at least 1 candy
Even child with rating 0 gets 1!
2. Only compare with DIRECT neighbors
Not all children, just left and right neighbors
3. Equal ratings can have different candies
ratings = [1, 2, 2]
candies = [1, 2, 1] ✓ Valid!
Equal ratings don't need equal candies!
4. Goal: MINIMIZE total candies
Give as few as possible while satisfying rules
The Challenge:
Why is this hard?
Example: ratings = [1, 2, 3, 4]
If we process left to right only:
Child 0: 1 candy
Child 1: 2 candies (1 > 2, so need 2)
Child 2: 3 candies (2 > 3, so need 3)
Child 3: 4 candies (3 > 4, so need 4)
Total: 10
But dependencies work BOTH ways:
- Child must have more than LEFT neighbor (if rating higher)
- Child must have more than RIGHT neighbor (if rating higher)
Can't satisfy both in single pass! 🤔
🧠 The AHA Moment - Two Pass Strategy
The Key Insight:
Problem: Can't satisfy left AND right constraints in one pass
Solution: Make TWO passes!
Pass 1: Satisfy LEFT neighbor constraints (left to right)
Pass 2: Satisfy RIGHT neighbor constraints (right to left)
Take the MAXIMUM from both passes!
Why this works:
- Pass 1 ensures: if rating > left neighbor, candies > left neighbor
- Pass 2 ensures: if rating > right neighbor, candies > right neighbor
- Maximum of both satisfies BOTH constraints! 🎯
Visual Discovery - Why Two Passes Work
Example: ratings = [1, 0, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PASS 1: Left to right (satisfy left neighbor constraints)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initialize: candies = [1, 1, 1] (minimum for each)
i=0: rating=1
No left neighbor
candies[0] = 1
i=1: rating=0
Left neighbor rating=1
0 < 1, so no constraint
candies[1] = 1
i=2: rating=2
Left neighbor rating=0
2 > 0, so need more candies than left!
candies[2] = candies[1] + 1 = 2
After Pass 1: candies = [1, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PASS 2: Right to left (satisfy right neighbor constraints)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Current: candies = [1, 1, 2]
i=2: rating=2
No right neighbor
candies[2] = max(2, 1) = 2
i=1: rating=0
Right neighbor rating=2
0 < 2, so no constraint
candies[1] = max(1, 1) = 1
i=0: rating=1
Right neighbor rating=0
1 > 0, so need more candies than right!
Need: candies[1] + 1 = 2
candies[0] = max(1, 2) = 2
After Pass 2: candies = [2, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Final: candies = [2, 1, 2]
Total: 2 + 1 + 2 = 5 ✓
Verification:
Child 0: rating=1 > rating[1]=0, candies=2 > candies[1]=1 ✓
Child 1: rating=0 < neighbors, candies=1 OK ✓
Child 2: rating=2 > rating[1]=0, candies=2 > candies[1]=1 ✓
All constraints satisfied! 🎯
Why Maximum of Both Passes?
Question: Why take max(pass1[i], pass2[i])?
Answer: We need to satisfy BOTH constraints!
Example: ratings = [1, 3, 2]
Pass 1 (left to right):
i=0: candies=1 (no left)
i=1: rating 3 > 1, candies=2 (more than left)
i=2: rating 2 < 3, candies=1 (no constraint from left)
Result: [1, 2, 1]
Pass 2 (right to left):
i=2: candies=1 (no right)
i=1: rating 3 > 2, need candies=2 (more than right)
i=0: rating 1 < 3, candies=1 (no constraint from right)
Result: [1, 2, 1]
Final: max([1,2,1], [1,2,1]) = [1, 2, 1]
Both passes gave same result!
But taking max ensures we satisfy BOTH left and right! ✓
Another Example Showing Why Max is Needed
ratings = [1, 2, 87, 87, 87, 2, 1]
Pass 1 (satisfy left constraints):
[1, 2, 3, 1, 1, 1, 1]
Why? 87 > 2, so need 3
Then equal ratings reset to 1
Pass 2 (satisfy right constraints):
[1, 2, 3, 1, 1, 2, 1]
Why? At position 5, rating 2 > 1
Need more than right
Final: max of both = [1, 2, 3, 1, 1, 2, 1]
Position 2 needs 3 from pass 1 (87 > 2 on left)
Position 5 needs 2 from pass 2 (2 > 1 on right)
Taking maximum ensures BOTH constraints met! 🎯
🟢 Approach: Two Pass Greedy (Optimal)
🎨 Building the Complete Solution
Step 1: Initialize with Minimum
Everyone gets at least 1 candy
candies = [1, 1, 1, ..., 1] (array of 1's)
This is our BASE case
Now we add more candies where needed to satisfy constraints
Step 2: Left Pass (Satisfy Left Neighbor Constraint)
For i from 1 to n-1:
If ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
This ensures:
Higher rating than left → more candies than left ✓
Step 3: Right Pass (Satisfy Right Neighbor Constraint)
For i from n-2 to 0:
If ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
Why max?
We already satisfied left constraint in pass 1
Now we satisfy right constraint
Need to maintain BOTH! So take maximum!
Step 4: Sum Total Candies
Total = sum of all candies array
This is the minimum candies needed! ✓
📝 Implementation - Clean and Clear
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
// Step 1: Initialize - everyone gets at least 1 candy
int[] candies = new int[n];
for (int i = 0; i < n; i++) {
candies[i] = 1;
}
// Step 2: Left to right pass
// Ensure: if rating > left neighbor, candies > left neighbor
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Step 3: Right to left pass
// Ensure: if rating > right neighbor, candies > right neighbor
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// Step 4: Calculate total candies
int total = 0;
for (int candy : candies) {
total += candy;
}
return total;
}
}
🔍 Complete Dry Run
Input: ratings = [1, 0, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Initialize
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
candies = [1, 1, 1]
Everyone starts with 1 candy (minimum)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Left to right pass
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Goal: Satisfy left neighbor constraints
i=1: ratings[1]=0, ratings[0]=1
0 > 1? NO
No change
candies = [1, 1, 1]
i=2: ratings[2]=2, ratings[1]=0
2 > 0? YES!
candies[2] = candies[1] + 1 = 1 + 1 = 2
candies = [1, 1, 2]
After left pass: candies = [1, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Right to left pass
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Goal: Satisfy right neighbor constraints
i=1: ratings[1]=0, ratings[2]=2
0 > 2? NO
No change
candies = [1, 1, 2]
i=0: ratings[0]=1, ratings[1]=0
1 > 0? YES!
Need: candies[1] + 1 = 1 + 1 = 2
candies[0] = max(1, 2) = 2
candies = [2, 1, 2]
After right pass: candies = [2, 1, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 4: Calculate total
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
total = 2 + 1 + 2 = 5 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
VERIFICATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ratings = [1, 0, 2]
candies = [2, 1, 2]
Child 0:
Rating: 1
Right neighbor rating: 0
1 > 0 ✓ and candies[0]=2 > candies[1]=1 ✓
Child 1:
Rating: 0 (lowest)
Candies: 1 (minimum) ✓
Child 2:
Rating: 2
Left neighbor rating: 0
2 > 0 ✓ and candies[2]=2 > candies[1]=1 ✓
All constraints satisfied! Answer: 5 ✓
Another Example - More Complex
Input: ratings = [1, 2, 2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
candies = [1, 1, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LEFT PASS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: ratings[1]=2 > ratings[0]=1? YES
candies[1] = candies[0] + 1 = 2
candies = [1, 2, 1]
i=2: ratings[2]=2 > ratings[1]=2? NO
No change
candies = [1, 2, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RIGHT PASS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: ratings[1]=2 > ratings[2]=2? NO
No change
candies = [1, 2, 1]
i=0: ratings[0]=1 > ratings[1]=2? NO
No change
candies = [1, 2, 1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
candies = [1, 2, 1]
total = 1 + 2 + 1 = 4 ✓
Note: Equal ratings (both 2) can have different candies!
ratings[1]=2 has 2 candies
ratings[2]=2 has 1 candy
This is VALID! No constraint for equal ratings!
📊 Complexity Analysis
Time Complexity: O(n)
Initialize array: O(n)
Left pass: O(n)
Right pass: O(n)
Sum calculation: O(n)
Total: O(n)
LINEAR TIME! Optimal! 🎯
Space Complexity: O(n)
Candies array: O(n)
Note: Could be optimized to O(1) with more complex logic,
but O(n) is clean and acceptable
💡 Why This Works - Deep Intuition
The Two-Direction Dependency Problem
Problem Explained:
Child i's candies depend on:
1. Left neighbor (if ratings[i] > ratings[i-1])
2. Right neighbor (if ratings[i] > ratings[i+1])
Example: ratings = [1, 3, 2]
Child 1 (rating 3):
Must have > candies than child 0 (rating 1) → dependency on left
Must have > candies than child 2 (rating 2) → dependency on right
Can't resolve BOTH in one pass! 🤔
Solution: Separate the Dependencies
Pass 1: Handle left dependencies ONLY
For each child: if rating > left, give more candies than left
Ignore right neighbor for now
Pass 2: Handle right dependencies ONLY
For each child: if rating > right, give more candies than right
BUT: Keep the candies from pass 1 if they're already higher!
Taking max ensures BOTH dependencies satisfied! ✓
Mathematical Proof
Claim: Two-pass algorithm gives minimum candies
Proof:
1. Each child gets at least 1 (initialized) ✓
2. After left pass:
If ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
This is MINIMUM needed to satisfy left constraint ✓
3. After right pass:
If ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
This maintains left constraint AND satisfies right constraint
With MINIMUM increase needed ✓
4. Since we use minimum at each step:
Final result is minimum total candies ✓
QED 🎯
🎯 Key Insights Summary
The Three Critical Points:
1. Two-Pass Strategy
Can't satisfy both neighbors in one pass!
Solution:
Pass 1: Left to right (left constraints)
Pass 2: Right to left (right constraints)
Take maximum to satisfy BOTH!
This decouples the dependencies! 🔑
2. Why Maximum?
We need to satisfy BOTH constraints:
- Higher than left (if rating > left)
- Higher than right (if rating > right)
Maximum ensures both are satisfied:
max(leftConstraint, rightConstraint)
This is the key to correctness! ✓
3. Greedy is Optimal
At each step, we give MINIMUM candies needed:
- Pass 1: Just enough to beat left neighbor
- Pass 2: Just enough to beat right neighbor
Never give more than necessary!
Therefore: Total is minimum! 🎯
⚠️ Common Mistakes
// Mistake 1: Single pass only
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i-1]) {
candies[i] = candies[i-1] + 1;
}
}
// ❌ Doesn't handle right neighbor constraints!
// ✓ CORRECT: Two passes
// Left pass + Right pass
// Mistake 2: Not using max in right pass
if (ratings[i] > ratings[i+1]) {
candies[i] = candies[i+1] + 1; // ❌ Overwrites left constraint!
}
// ✓ CORRECT:
candies[i] = Math.max(candies[i], candies[i+1] + 1);
// Mistake 3: Wrong pass direction
// Left pass going right to left ❌
// Right pass going left to right ❌
// ✓ CORRECT:
// Left pass: left to right (i++)
// Right pass: right to left (i--)
// Mistake 4: Comparing with all children
if (ratings[i] > ratings[j]) { // for all j ❌
// ✓ CORRECT: Only direct neighbors!
if (ratings[i] > ratings[i-1]) // left
if (ratings[i] > ratings[i+1]) // right
📝 Quick Revision Notes
🎯 Core Concept
Problem: Give candies to children with rating constraints
Constraints: 1. Everyone gets ≥ 1 candy 2. Higher rating than neighbor → more candies than that neighbor
Key Insight: Two-pass strategy separates left and right dependencies!
Algorithm: 1. Initialize all to 1 2. Left pass: satisfy left constraints 3. Right pass: satisfy right constraints (take max!) 4. Sum total
Why It Works: Maximum ensures BOTH constraints met with minimum candies!
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int candy(int[] ratings) {
return greedy(ratings);
}
private int greedy(int[] a) {
// Approach
// step 1: assign 1 candy to each child initially
// pass 1: from left to right
// if current child's rating is more than the child
// on left side, increase by 1 and assign those many candies.
// pass 2: from right to left
// if current child's rating is more than the child
// on RIGHT side, increase by 1 and assign those many candies.
// pass 3: result array is max among these 2 passes
// pass 2 and pass 3 can be combined
int n = a.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
// pass 1
for (int i = 1; i < n; i++) {
// GREATER ONLY (EQUALS also does not apply)
if (a[i] > a[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// pass 2 and 3
for (int i = n - 2; i >= 0; i--) {
if (a[i] > a[i + 1]) {
// check if already assigned is greater (due to pass 1)
// than the incoming from pass 2.
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
return Arrays.stream(candies).sum();
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.candy(new int[] { 1, 0, 2 }) == 5);
System.out.println(s.candy(new int[] { 1, 2, 2 }) == 4);
}
}
🔑 Key Points
✓ Two passes: left-to-right, right-to-left
✓ Initialize all to 1 (minimum)
✓ Left pass: if rating > left, candies = left + 1
✓ Right pass: if rating > right, candies = max(current, right + 1)
✓ Maximum ensures BOTH constraints satisfied
✓ Time: O(n), Space: O(n)
✓ Greedy gives optimal (minimum candies)
🎪 Memory Aid
"Two passes solve the maze!"
"Left then right, both ways we gaze!"
"Maximum keeps constraints in phase!"
"Greedy minimum, candies we raise!" ✨
🎉 Congratulations!
You've mastered Candy - a Hard problem!
What You Learned:
✅ Two-pass strategy - Separate dependencies
✅ Greedy optimization - Minimum at each step
✅ Maximum combination - Satisfy both constraints
✅ Bidirectional constraints - Left and right
✅ Proof of correctness - Why greedy is optimal
The Beautiful Insight:
Complex Bidirectional Constraint → Simple Two-Pass Solution
The core insight:
"Can't satisfy left AND right in one pass"
"Dependencies point in opposite directions"
Solution:
Pass 1: Handle left dependencies
Pass 2: Handle right dependencies
Take MAXIMUM to satisfy BOTH!
This decoupling strategy:
- Simplifies the problem
- Each pass is simple greedy
- Maximum combines results
- Optimal solution emerges! 🎯
This pattern appears in:
- Rain Water Trapping (similar two-pass)
- Stock prices (multiple passes)
- Any bidirectional dependency problem
Master this pattern = Solve many problems! ✨
Interview Mastery:
When asked about Candy:
1. Understand: "Minimum candies with rating constraints"
2. Identify challenge: "Each child depends on BOTH neighbors.
Can't resolve in single pass!"
3. Key insight: "Two-pass strategy!
Pass 1: Handle left neighbor constraints
Pass 2: Handle right neighbor constraints
Take maximum to satisfy both!"
4. Why optimal: "Each pass gives minimum needed.
Maximum combines minimum from both directions.
Result is global minimum!"
5. Code it: Clean O(n) solution with two passes
6. Complexity: "O(n) time for two passes, O(n) space for array."
7. Edge cases: "Single child, all same ratings, etc."
Shows complete understanding! 💯
You've mastered a Hard-rated greedy problem with bidirectional constraints! 🚀✨🎯