Two-Pass Assignment

There are n children standing in a line. Each child has a rating. You need to give candies to these children subject to two rules: every child must get at least one candy, and any child with a higher rating than their neighbor must get more candies than that neighbor. What is the minimum total number of candies you need?

This is LeetCode 135, "Candy," and it is the definitive example of the two-pass assignment pattern. The problem sounds simple, but if you try to solve it with a single sweep, you will quickly discover why that does not work, and why two passes are the natural fix.

Why a single pass fails

Suppose you walk left to right, giving each child the minimum candies needed to beat their left neighbor. When you reach a child whose rating is higher than the child to their left, you give them one more candy than that left neighbor. When the rating drops or stays the same, you reset to 1. This correctly enforces the left-neighbor constraint.

But what about the right-neighbor constraint? Consider ratings [1, 2, 2, 3, 2, 1]. Walking left to right and only looking at left neighbors, you might produce candies [1, 2, 1, 2, 1, 1]. Now look at index 4 (rating 2) and index 5 (rating 1). Child 4 has a higher rating than child 5 but they both got 1 candy. That violates the rules. Worse, look at index 3 (rating 3) and index 4 (rating 2): child 3 should have more candies than child 4, so child 3 needs at least 3 candies, not 2. The left-to-right pass had no way to know this because the information about the descending sequence to the right had not been processed yet.

You could try to fix this by backtracking when you discover a violation, but that leads to messy logic and potentially $O(n^2)$ behavior. The two-pass approach is cleaner and stays $O(n)$.

The two-pass solution

The idea is to separate the two constraints and handle each one independently.

Pass 1 (left to right): Create an array candies initialized to all 1s. Walk from index 1 to n-1. If ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1. Otherwise, leave it at 1. After this pass, every child who has a higher rating than their left neighbor has more candies than that left neighbor.

Pass 2 (right to left): Walk from index n-2 down to 0. If ratings[i] > ratings[i+1] and candies[i] <= candies[i+1], set candies[i] = candies[i+1] + 1. After this pass, every child who has a higher rating than their right neighbor also has more candies than that right neighbor.

The key correctness insight: taking the max of both directional requirements at each position is not a heuristic. It is exact. If the left-to-right pass says child i needs at least 3 candies and the right-to-left pass says child i needs at least 5, then giving them 5 satisfies both constraints simultaneously. In the implementation above, we do this implicitly: the second pass only increases values, never decreases them.

Worked example: ratings = [1, 0, 2]

Start with candies = [1, 1, 1].

Left-to-right pass: index 1 has rating 0, which is not greater than rating 1 at index 0, so no change. Index 2 has rating 2, which is greater than rating 0 at index 1, so candies[2] = candies[1] + 1 = 2. Now candies = [1, 1, 2].

Right-to-left pass: index 1 has rating 0, which is not greater than rating 2 at index 2, so no change. Index 0 has rating 1, which is greater than rating 0 at index 1, and candies[0] (1) <= candies[1] (1), so candies[0] = candies[1] + 1 = 2. Now candies = [2, 1, 2].

Total: 2 + 1 + 2 = 5. Child 0 (rating 1) has more candies than child 1 (rating 0). Child 2 (rating 2) has more candies than child 1 (rating 0). Both constraints satisfied with minimum total.

Worked example: ratings = [1, 2, 2, 3, 2, 1]

Start with candies = [1, 1, 1, 1, 1, 1].

Left-to-right pass:

• Index 1: rating 2 > rating 1 at index 0, so candies[1] = 2
• Index 2: rating 2 is not greater than rating 2 at index 1, no change
• Index 3: rating 3 > rating 2 at index 2, so candies[3] = candies[2] + 1 = 2
• Index 4: rating 2 is not greater than rating 3, no change
• Index 5: rating 1 is not greater than rating 2, no change

After left-to-right: candies = [1, 2, 1, 2, 1, 1].

Right-to-left pass:

• Index 4: rating 2 > rating 1 at index 5, and candies[4] (1) <= candies[5] (1), so candies[4] = 2
• Index 3: rating 3 > rating 2 at index 4, and candies[3] (2) <= candies[4] (2), so candies[3] = 3
• Index 2: rating 2 is not greater than rating 3, no change
• Index 1: rating 2 is not greater than rating 2, no change (equal ratings do not require more candies)
• Index 0: rating 1 is not greater than rating 2, no change

After right-to-left: candies = [1, 2, 1, 3, 2, 1].

Total: 1 + 2 + 1 + 3 + 2 + 1 = 10. Every constraint is satisfied. Child 3 with the highest local rating gets the most candies in its neighborhood.

Code: Candy

def candy(ratings):
    n = len(ratings)
    candies = [1] * n

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

    # Right to left: enforce 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)

Notice the max in the second pass. We do not blindly set candies[i] = candies[i+1] + 1. We take the maximum of the existing value and the new one. The existing value already enforces the left constraint; the new value enforces the right constraint. The max of both enforces both.

Trapping Rain Water

LeetCode 42 applies the same two-pass skeleton to an entirely different problem. Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

The water above any bar at position i is determined by the minimum of two values: the tallest bar to its left and the tallest bar to its right. Specifically, water[i] = max(0, min(left_max[i], right_max[i]) - height[i]). The water level at each position is capped by the shorter of the two "walls" enclosing it, and we subtract the bar's own height since it displaces water.

The information from both directions, the maximum height seen from the left and the maximum height seen from the right, is exactly the two-pass pattern.

Worked example: heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Left-to-right pass to build left_max:

• left_max[0] = 0, left_max[1] = 1, left_max[2] = 1, left_max[3] = 2, left_max[4] = 2, left_max[5] = 2, left_max[6] = 2, left_max[7] = 3, left_max[8] = 3, left_max[9] = 3, left_max[10] = 3, left_max[11] = 3

Right-to-left pass to build right_max:

• right_max[11] = 1, right_max[10] = 2, right_max[9] = 2, right_max[8] = 2, right_max[7] = 3, right_max[6] = 3, right_max[5] = 3, right_max[4] = 3, right_max[3] = 3, right_max[2] = 3, right_max[1] = 3, right_max[0] = 3

Water at each position: min(left_max[i], right_max[i]) - height[i] if positive.

• Index 2: min(1, 3) - 0 = 1
• Index 4: min(2, 3) - 1 = 1
• Index 5: min(2, 3) - 0 = 2
• Index 6: min(2, 3) - 1 = 1
• Index 9: min(3, 2) - 1 = 1
• Index 11: min(3, 1) - 1 = 0

Total water: 1 + 1 + 2 + 1 + 1 + 0 = 6. (The exact total for this classic example is 6.)

Code: Trapping Rain Water

def trap(height):
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]
    return water

The two-pointer optimization for trapping rain water

The two-pass solution uses $O(n)$ space for the two auxiliary arrays. We can reduce this to $O(1)$ using two pointers.

The insight is that the water at any position depends on min(left_max, right_max). If we maintain a left pointer and a right pointer starting at opposite ends, and we know left_max and right_max at those pointers, then whichever side has the smaller max determines the water level. If left_max < right_max, we know the water at the left pointer is determined by left_max regardless of what the true right_max is (it can only be >= the right_max we have tracked), so we can safely process the left pointer and advance it. Symmetrically for the right side.

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

This runs in $O(n)$ time and $O(1)$ space. Each pointer moves at most n times total, and at each step we do constant work. The logic is trickier to get right than the two-pass version, so in an interview it is worth presenting the two-pass solution first, then offering this as an optimization.

Product of Array Except Self

For LeetCode 238, you are given an array nums and must return an array where answer[i] is the product of all elements in nums except nums[i]. You must do it without using division.

The "without division" constraint is what makes this interesting. If division were allowed, you could compute the total product and divide by each element. Without it, you need another approach.

The two-pass idea: the product of everything except nums[i] is the product of everything to its left multiplied by the product of everything to its right. We can compute left-prefix products in a left-to-right pass and right-suffix products in a right-to-left pass, then multiply them together.

For nums = [1, 2, 3, 4]:

• Left products: [1, 1, 2, 6], where left[i] is the product of all elements before index i
• Right products: [24, 12, 4, 1], where right[i] is the product of all elements after index i
• Answer: [1*24, 1*12, 2*4, 6*1] = [24, 12, 8, 6]

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n

    # Left pass: answer[i] accumulates product of nums[0..i-1]
    left_product = 1
    for i in range(n):
        answer[i] = left_product
        left_product *= nums[i]

    # Right pass: multiply in product of nums[i+1..n-1]
    right_product = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right_product
        right_product *= nums[i]

    return answer

This version is particularly elegant: it uses the output array itself to store the left products, then multiplies in the right products during the second pass. The only extra space is the two scalar variables left_product and right_product, so it runs in $O(1)$ auxiliary space.

The general pattern

All three problems share the same structure: the correct value at position i depends on information gathered from both the left side and the right side of the array. A single pass in one direction can only capture one side. Two passes, one in each direction, capture both, and combining their results gives the full answer.

When you encounter a new problem, ask yourself: does the answer at each index depend on some aggregate (max, min, product, count) from both directions? If so, you are looking at a two-pass problem. The template is always the same:

1. Allocate space for left-to-right results (an array or a running variable)
2. Sweep left to right, computing each position's value based on the left context
3. Sweep right to left, computing each position's value based on the right context
4. Combine the two results, typically with max, min, multiplication, or addition

The combination operator depends on the problem semantics. For Candy, it is max (the child needs the larger of both constraints). For Trapping Rain Water, it is min (water level is capped by the shorter wall). For Product Except Self, it is multiplication (left product times right product).

Complexity

All three problems run in $O(n)$ time: two linear passes plus a linear combination step. Space is $O(n)$ for the basic versions (the auxiliary arrays), but can often be reduced to $O(1)$ with the two-pointer trick (Trapping Rain Water) or by reusing the output array (Product Except Self). The Candy problem inherently needs $O(n)$ space for the output, though you can fold the two arrays into one.

The two-pass pattern is one of the most satisfying techniques in array problems. Once you see that the answer at each position is the combination of a left aggregate and a right aggregate, the code almost writes itself.

Recognizing this pattern

You're probably looking at two-pass assignment when:

• You need to produce an output array of the same length as the input, where each position's answer depends on both sides of itself.
• A single left-to-right (or right-to-left) sweep gives you only half the information. The value at $i$ is some combination of an aggregate over $[0, i-1]$ and another over $[i+1, n-1]$.
• The combining function is associative and simple: max, min, sum, product, count.
• Division is forbidden, or the problem includes zeros, or the per-position constraint is "must satisfy both a left neighbor rule and a right neighbor rule."
• Sorting would destroy positional meaning, so you're stuck operating in place.

Common templates:

• Left-max and right-max bounded by min: the classic rain-water silhouette. Example: Trapping Rain Water.
• Left and right monotone constraints combined with max: ratings or comparisons that must respect both neighbors. Example: Candy.
• Prefix product times suffix product: building the "everything except me" aggregate without division. Example: Product of Array Except Self.
• Daily temperatures-style "next greater" with a backward pass: answer at $i$ depends on a future scan. Example: Daily Temperatures.
• Shortest path in a binary grid from both ends / first-and-last position: left-to-right and right-to-left sweeps combined for boundary info. Example: Shortest Unsorted Continuous Subarray.