Candy — Two-Pass Greedy Rating Satisfaction [LC 135]

Problem Statement#

There are n children with ratings. Give each child at least 1 candy. Children with a higher rating than their adjacent neighbor must receive more candies. Find the minimum total candies needed.

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 135 is a hard-difficulty greedy problem asked at Amazon, Google, and Microsoft. The brute-force multi-pass approach works but is inelegant. The optimal two-pass solution demonstrates a key insight: decompose the constraint into two independent left-right constraints and satisfy each independently.

The problem tests whether you can handle constraints from multiple directions simultaneously — a pattern that recurs in problems like Trapping Rain Water (LC 42) and Container with Most Water. The "left pass + right pass + take max" structure is a valuable template.

The Core Insight#

Decompose the constraint:

• Left constraint: if ratings[i] > ratings[i-1], child i must get more than child i-1
• Right constraint: if ratings[i] > ratings[i+1], child i must get more than child i+1

Two-pass algorithm:

1. Initialize all candies to 1
2. Left-to-right pass: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1
3. Right-to-left pass: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1)
4. Sum all candies

The max in step 3 is crucial: we never reduce what the left pass already granted — we only increase if the right constraint requires more.

Visual Dry Run#

ratings = [1, 0, 2]

Initial: [1, 1, 1]

Left pass: ratings[1]=0 < ratings[0]=1 — no change. ratings[2]=2 > ratings[1]=0 — candies[2] = candies[1]+1 = 2 After left pass: [1, 1, 2]

Right pass (right to left): ratings[1]=0 < ratings[2]=2 — no change. ratings[0]=1 > ratings[1]=0 — candies[0] = max(1, candies[1]+1) = max(1, 2) = 2 After right pass: [2, 1, 2]

Total: 2 + 1 + 2 = 5

Solution (Optimal)#

class Solution:
    def candy(self, ratings):
        n = len(ratings)
        candies = [1] * n
        # Left-to-right: satisfy left neighbor constraint
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        # Right-to-left: satisfy right neighbor constraint
        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)

var candy = function(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    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((a, b) => a + b, 0);
};

Time: O(n) — two linear passes Space: O(n) — candies array

Common Mistakes#

• Single-pass approach — cannot satisfy both left and right constraints simultaneously in one pass without revisiting
• Right-to-left pass sets instead of taking max — must not reduce what the left pass granted
• Not initializing all candies to 1 — every child must receive at least 1 candy
• Using >= instead of > — equal ratings don't require different candy counts
• Forgetting the right pass entirely — only satisfying the left constraint misses half the problem

Interview Tips#

• Explain the decomposition: "left pass satisfies left constraint independently, right pass satisfies right constraint"
• Emphasize the max in the right pass: "we take max, never reduce — the left constraint is already satisfied"
• Trace through [1, 2, 87, 87, 87, 2, 1] to show both passes handle the valley correctly
• An O(1) space solution exists using slope counting — mention it if asked for follow-up, but explain it's much harder
• The two-pass template: "left-to-right + right-to-left + take max" appears in Trapping Rain Water too

Follow-up Questions#

• Can you solve it in O(1) space? (Yes — analyze slopes: count up-slope and down-slope lengths, use the formula peak * (peak-1)/2 for each slope)
• What if equal ratings also require equal or more candies? (Change > to >= in both passes — equal neighbors must have equal or more)
• How does this relate to Trapping Rain Water (LC 42)? (Both use left-max and right-max arrays computed in two passes, then combine with max/min)
• What if the children are arranged in a circle? (The two-pass approach needs modification — circular constraints are more complex)
• Can there be multiple optimal distributions? (Yes — the problem asks for minimum total, not unique distribution)

Key Takeaways#

• LeetCode 135 is asked at Amazon, Google, and Microsoft — hard greedy with elegant two-pass decomposition
• Decompose into two independent constraints: left-neighbor and right-neighbor
• Left pass: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1
• Right pass: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1) — always take max
• Time O(n), Space O(n) — two passes with a candies array
• The max operation in the right pass is crucial: never reduce what the left pass established
• The "two-pass + take max" template directly applies to Trapping Rain Water and other bidirectional constraint problems