Candy - Two-Pass Greedy Walkthrough

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

You are given an integer array ratings. Assign candies to each child such that:

Each child has at least one candy
If ratings[i] > ratings[i-1], then child i must get more than i-1
If ratings[i] > ratings[i+1], then child i must get more than i+1

Return the minimum total candies needed.

Examples

Example 1:
Input: ratings = [1,0,2]
Output: 5
Distribution: [2,1,2]

Example 2:
Input: ratings = [1,2,2]
Output: 4
Distribution: [1,2,1]

Constraints

1 <= ratings.length <= 2 * 10^4
0 <= ratings[i] <= 2 * 10^4

🎯 Real-World Analogy

Performance Bonus Seating Row

Imagine a row of teammates receiving bonus points. Everyone gets at least 1 point. If someone performed better than their immediate neighbor, they must receive more points.

One pass left-to-right handles "better than left neighbor". Another pass right-to-left handles "better than right neighbor". Combining both satisfies both constraints with minimal inflation.

💡 Key Insights

Local constraints come from both directions, so one directional pass is insufficient.
Initialize all candies to 1 to satisfy base rule.
Left pass enforces increasing slopes from left neighbors.
Right pass corrects descending slopes from right neighbors using max.
Greedy works because each pass only adjusts what is necessary to satisfy local inequalities.

💻 Solution Approaches

Approach 1: Repeated Relaxation

Time: O(N²) worst case | Space: O(N)

Repeatedly scan and fix violations until stable. Correct but too slow and overcomplicated.

Approach 2: Two-Pass Greedy (Recommended)

Time: O(N) | Space: O(N)

Enforce left constraints in first pass, right constraints in second pass.

Python Implementation

          from typing import List


def candy(ratings: List[int]) -> int:
    """
    Return minimum candies satisfying neighbor constraints.

    Time: O(N)
    Space: O(N)
    """
    n = len(ratings)
    candies = [1] * n

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

    # Right to left: enforce ratings[i] > ratings[i+1]
    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)
        

JavaScript Implementation

          function candy(ratings) {
  /**
   * Return minimum candies satisfying neighbor constraints.
   *
   * Time: O(N)
   * Space: O(N)
   */
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  // Left to right
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  // Right to left
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  return candies.reduce((sum, value) => sum + value, 0);
}
        

🔍 Step-by-Step Walkthrough

Trace ratings = [1,0,2]:

Init: candies = [1, 1, 1]

            Left pass:

            i=1: 0 > 1? no -> [1,1,1]

            i=2: 2 > 0? yes -> candies[2]=2 -> [1,1,2]
          
            Right pass:

            i=1: 0 > 2? no -> [1,1,2]

            i=0: 1 > 0? yes -> candies[0]=max(1,1+1)=2 -> [2,1,2]
          
            Total: 2 + 1 + 2 = 5

⚡ Complexity Analysis

Time Complexity: O(N)

Two linear passes over ratings, each O(N).

Space Complexity: O(N)

We store one candy count per child.

🔧 Edge Cases

Single child: answer is always 1
All equal ratings: everyone gets 1
Strictly increasing ratings
Strictly decreasing ratings
Peaks and valleys like [1,3,2,2,1]

🧪 Test Cases

Python

          def test_candy():
    assert candy([1, 0, 2]) == 5
    assert candy([1, 2, 2]) == 4
    assert candy([1]) == 1
    assert candy([1, 1, 1]) == 3
    assert candy([1, 2, 3, 4]) == 10
    assert candy([4, 3, 2, 1]) == 10
    assert candy([1, 3, 2, 2, 1]) == 7

    print("✅ all tests passed")
        

JavaScript

          function testCandy() {
  console.assert(candy([1, 0, 2]) === 5, "test 1");
  console.assert(candy([1, 2, 2]) === 4, "test 2");
  console.assert(candy([1]) === 1, "test 3");
  console.assert(candy([1, 1, 1]) === 3, "test 4");
  console.assert(candy([1, 2, 3, 4]) === 10, "test 5");
  console.assert(candy([4, 3, 2, 1]) === 10, "test 6");
  console.assert(candy([1, 3, 2, 2, 1]) === 7, "test 7");

  console.log("✅ all tests passed");
}
        

💼 Interview Tips

Explain why one pass fails: it cannot enforce both neighbor directions.
State the invariant after each pass.
Use max in right pass to preserve left-pass constraints.
Draw one valley/peak example to prove minimality intuition.
Mention optimized O(1)-space slope-count variant only after clear O(N)-space solution.

🎓 Key Takeaways

Two-pass greedy is the clean way to satisfy bidirectional local constraints.
Initialization to 1 handles base feasibility, passes handle optimal adjustments.
This pattern appears in problems with left and right dependency constraints.

← Back to All Algorithms