LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Greedy Algorithm/Candy Problem: Why Two-Pass Greedy Works (And Why One Pass Fails)

Candy Problem: Why Two-Pass Greedy Works (And Why One Pass Fails)

LeetCopilot Team
Dec 30, 2025
8 min read
Greedy AlgorithmTwo-PassCandy ProblemBidirectional ConstraintsInterview Prep
Master the two-pass greedy technique for the Candy problem. Learn why one pass fails, understand the bidirectional constraint pattern, and see the complete solution.
Complete Guide

The Complete Greedy Algorithm Guide: Master All Patterns, Proofs, and Recognition Techniques

The ultimate comprehensive guide to greedy algorithms. Learn all patterns (interval scheduling, sorting, state tracking), when to use greedy vs DP, complete templates in multiple languages, proof techniques, and a systematic approach to solve any greedy problem.

Read the complete guide

The Candy problem (LeetCode #135) is a classic example of when one-pass greedy fails but two-pass greedy works.

Understanding why teaches you a powerful pattern for problems with bidirectional constraints.

TL;DR

Problem: Distribute candies such that each child gets at least 1, and children with higher ratings get more than neighbors.

Why one pass fails: Can't satisfy both left and right constraints simultaneously.

Two-pass solution:

  1. Left-to-right: Ensure right neighbor gets more if rated higher
  2. Right-to-left: Ensure left neighbor gets more if rated higher

Time: O(n), Space: O(n)

The Problem

LeetCode #135: Candy

Given ratings, distribute candies such that:

  1. Each child gets at least 1 candy
  2. Children with higher rating get more than neighbors
code
Input: [1,2,3,2,1]
Output: 9
Candies: [1,2,3,2,1]

Why One Pass Fails

Attempt: Left-to-Right Only

python
def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    
    # Left to right
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    return candies

# Example
ratings = [1, 2, 3, 2, 1]
print(candy(ratings))  # [1, 2, 3, 1, 1]

Problem:

code
Ratings:  [1, 2, 3, 2, 1]
Candies:  [1, 2, 3, 1, 1]
                    ↑  ↑
Child at index 3 (rating=2) has 1 candy
Child at index 4 (rating=1) has 1 candy
But rating[3] > rating[4], so candies[3] should > candies[4] ✗

Attempt: Right-to-Left Only

python
def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    
    # Right to left
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = candies[i+1] + 1
    
    return candies

# Example
ratings = [1, 2, 3, 2, 1]
print(candy(ratings))  # [1, 1, 2, 2, 1]

Problem:

code
Ratings:  [1, 2, 3, 2, 1]
Candies:  [1, 1, 2, 2, 1]
           ↑  ↑
Child at index 0 (rating=1) has 1 candy
Child at index 1 (rating=2) has 1 candy
But rating[1] > rating[0], so candies[1] should > candies[0] ✗

The Two-Pass Solution

python
def candy(ratings: List[int]) -> int:
    """
    Two-pass greedy for Candy problem.
    Time: O(n), Space: O(n)
    """
    n = len(ratings)
    candies = [1] * n
    
    # Pass 1: Left to right
    # Ensure right neighbor gets more if rated higher
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    # Pass 2: Right to left
    # Ensure left neighbor gets more if rated higher
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
    
    return sum(candies)

# Example
print(candy([1,2,3,2,1]))  # 9
# After pass 1: [1,2,3,1,1]
# After pass 2: [1,2,3,2,1]
# Sum: 9

Step-by-Step Trace

code
Ratings: [1, 2, 3, 2, 1]

Initial: [1, 1, 1, 1, 1]

Pass 1 (left to right):
  i=1: ratings[1]=2 > ratings[0]=1
    candies[1] = candies[0] + 1 = 2
    [1, 2, 1, 1, 1]
  
  i=2: ratings[2]=3 > ratings[1]=2
    candies[2] = candies[1] + 1 = 3
    [1, 2, 3, 1, 1]
  
  i=3: ratings[3]=2 < ratings[2]=3
    No change
    [1, 2, 3, 1, 1]
  
  i=4: ratings[4]=1 < ratings[3]=2
    No change
    [1, 2, 3, 1, 1]

Pass 2 (right to left):
  i=3: ratings[3]=2 > ratings[4]=1
    candies[3] = max(1, 1+1) = 2
    [1, 2, 3, 2, 1]
  
  i=2: ratings[2]=3 > ratings[3]=2
    candies[2] = max(3, 2+1) = 3
    [1, 2, 3, 2, 1]
  
  i=1: ratings[1]=2 < ratings[2]=3
    No change
    [1, 2, 3, 2, 1]
  
  i=0: ratings[0]=1 < ratings[1]=2
    No change
    [1, 2, 3, 2, 1]

Final: [1, 2, 3, 2, 1]
Sum: 9 ✓

Proof of Correctness

Claim: Two-pass greedy gives minimum candies satisfying all constraints.

Proof:

Pass 1 ensures:

  • For all i: if ratings[i] > ratings[i-1], then candies[i] > candies[i-1] ✓

Pass 2 ensures:

  • For all i: if ratings[i] > ratings[i+1], then candies[i] > candies[i+1] ✓
  • Using max preserves pass 1 constraints ✓

Both constraints satisfied:

  • Each child with higher rating than left neighbor has more candies (pass 1)
  • Each child with higher rating than right neighbor has more candies (pass 2)
  • All constraints satisfied ✓

Minimality:

  • Pass 1 gives minimum candies for left constraints
  • Pass 2 adjusts only when necessary (using max)
  • Result is minimum ✓

Why max() in Pass 2?

Critical: In pass 2, we use max(candies[i], candies[i+1] + 1), not just candies[i + 1] + 1.

Why?

  • Pass 1 already set candies[i] based on left constraint
  • Pass 2 might require higher value for right constraint
  • We need both constraints satisfied
  • max() ensures we don't violate pass 1 while satisfying pass 2

Example:

code
Ratings: [1, 3, 2]

After pass 1: [1, 2, 1]
  (candies[1] = 2 because ratings[1] > ratings[0])

Pass 2, i=1:
  ratings[1]=3 > ratings[2]=2
  candies[1] = max(2, 1+1) = max(2, 2) = 2 ✓
  (If we used just candies[2]+1=2, we'd get same result)
  (But max ensures we don't decrease from pass 1)

Common Mistakes

Mistake 1: One Pass Only

❌ Wrong:

python
# Only left-to-right
for i in range(1, n):
    if ratings[i] > ratings[i-1]:
        candies[i] = candies[i-1] + 1

✅ Correct:

python
# Both passes
for i in range(1, n):
    if ratings[i] > ratings[i-1]:
        candies[i] = candies[i-1] + 1

for i in range(n-2, -1, -1):
    if ratings[i] > ratings[i+1]:
        candies[i] = max(candies[i], candies[i+1] + 1)

Mistake 2: Not Using max() in Pass 2

❌ Wrong:

python
candies[i] = candies[i+1] + 1  # Overwrites pass 1!

✅ Correct:

python
candies[i] = max(candies[i], candies[i+1] + 1)

Conclusion

Two-pass greedy solves problems with bidirectional constraints.

Pattern:

  1. Pass 1: Handle constraints from one direction
  2. Pass 2: Handle constraints from other direction (using max to preserve pass 1)

For more advanced greedy techniques, see Advanced Greedy Techniques and the complete greedy guide.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials