Candy — LeetCode 135 Two-Pass Greedy for Minimum Distribution

Problem Statement#

There are n children with rating values. Give candies so that each child gets at least 1, and any child with a strictly higher rating than a neighbor gets more candies than that neighbor. Return the minimum total candies.

Constraints:

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

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

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

Why This Problem Matters#

Candy is a classic Hard at Amazon, Google, Apple, and Bloomberg. It tests whether you can decompose a global constraint into two independent local sweeps. Most candidates start with "give 1 to lowest, then BFS outward" and burn 30 minutes; the two-pass solution lands in under 10.

This problem is heavily used at Amazon SDE2/SDE3 onsite for its O(1) extra-space follow-up. Apple has been seen asking candidates to optimize the two-pass to a single pass with valley counting.

The skill transfers to Trapping Rain Water (left/right max) and to many DP-on-array problems where you decompose two-direction constraints.

The Core Insight#

Each child's candy count must satisfy two constraints: greater than left neighbor when their rating is greater, and greater than right neighbor when their rating is greater. These are independent — sweep left-to-right enforcing the first, sweep right-to-left enforcing the second, then take the elementwise max.

Why max? If the left-pass said "child i needs 4" and the right-pass said "child i needs 7", child i needs at least 7 to satisfy both directions. The max never violates either constraint.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def candy(self, ratings):
        n = len(ratings)
        left = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        right = 1
        total = max(left[-1], 1)
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right += 1
            else:
                right = 1
            total += max(left[i], right)
        return total

var candy = function(ratings) {
    const n = ratings.length;
    const left = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
    }
    let right = 1;
    let total = Math.max(left[n - 1], 1);
    for (let i = n - 2; i >= 0; i--) {
        right = ratings[i] > ratings[i + 1] ? right + 1 : 1;
        total += Math.max(left[i], right);
    }
    return total;
};

Time: O(n) — two passes Space: O(n) for the left array; can be reduced to O(1) with valley counting

Common Mistakes#

• Using a single pass left-to-right — fails on descending suffixes like [3,2,1]
• Using >= instead of > — rule is "strictly greater rating, strictly more candy"
• Initializing all to 0 instead of 1 — every child needs at least 1
• Forgetting to take max in the right pass — undercount on local peaks
• Treating equal-rating neighbors as constrained — they are not, free to be equal or unequal

Interview Tips#

• Two passes beats trying to be clever in one pass — propose it openly
• Mention the O(1) follow-up: count up-runs and down-runs and use the formula k*(k+1)/2
• Sketch the rating curve to show why local maxima need the max of both directions

Follow-up Questions#

• Reduce space to O(1)? Hint: count consecutive ups and downs, plus the peak height
• What if ties allow strictly less? Hint: change the comparison and re-derive
• Two children can be equal in candies even with different ratings? Hint: only when ratings are equal
• Stream version with k newest children? Hint: maintain a deque of slopes
• What if you want max instead of min total? Hint: trivially unbounded, ill-posed

Key Takeaways#

• LeetCode 135 Candy is solved in O(n) with two passes plus elementwise max
• Each direction independently enforces one neighbor constraint
• Take max of left and right pass at each index, then sum
• Equal ratings are unconstrained — neighbors can have any difference
• O(1) space is achievable with valley counting plus arithmetic series formula
• Same template as Trapping Rain Water (left max + right max)
• Avoid the single-pass trap; FAANG graders specifically check the descending case