Candy: Two-Pass Greedy Distribution

There are n children standing in a line, each with an integer rating. You need to distribute candies with two rules: every child gets at least one candy, and any child with a higher rating than a neighbor must get more candies than that neighbor. Return the minimum total number of candies.

This is LeetCode 135: Candy, a hard problem that seems to require careful bookkeeping but collapses into a clean two-pass greedy solution once you see the core insight. Each pass handles one direction of the neighbor constraint, and you combine them with a single max operation.

Why this problem matters

Candy is one of the best examples of forward-backward constraint satisfaction. Many problems require you to enforce constraints that depend on both left and right neighbors. Trying to handle both directions in a single pass leads to complicated logic and edge cases. Splitting the work into two passes, one per direction, simplifies everything.

The two-pass pattern shows up in problems like Trapping Rain Water, Product of Array Except Self, and any scenario where each position depends on information from both sides. Mastering it here makes those problems feel familiar.

The brute force approach

The most natural approach is to iterate repeatedly, adjusting candy counts until all constraints are satisfied.

def candy_brute(ratings):
    n = len(ratings)
    candies = [1] * n
    changed = True
    while changed:
        changed = False
        for i in range(n):
            if i > 0 and ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
                candies[i] = candies[i - 1] + 1
                changed = True
            if i < n - 1 and ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
                candies[i] = candies[i + 1] + 1
                changed = True
    return sum(candies)

This works, but each pass may only fix one violation, and in the worst case you need O(n) passes through the array. That gives O(n^2) time. For inputs up to 2 * 10^4 children, this is too slow. The issue is that fixing one child's count can invalidate a neighbor you already processed.

The key insight: split the constraints by direction

Each child has at most two neighbors. The constraint says: if your rating is higher than a neighbor, you must have more candies than that neighbor. You can decompose this into two independent requirements:

1. Left constraint: if ratings[i] is greater than ratings[i - 1], then candies[i] must be greater than candies[i - 1].
2. Right constraint: if ratings[i] is greater than ratings[i + 1], then candies[i] must be greater than candies[i + 1].

Handle each constraint in its own pass. The left-to-right pass ensures every child has more candies than its left neighbor when appropriate. The right-to-left pass does the same for the right neighbor. Taking the max of both passes at each position satisfies both constraints simultaneously with the minimum possible candies.

Walking through it step by step

Let's trace through ratings = [1, 0, 2]. The answer is 5 with candies = [2, 1, 2].

The left-to-right pass catches the case where child 2 (rating 2) needs more than child 1 (rating 0). The right-to-left pass catches the case where child 0 (rating 1) needs more than child 1 (rating 0). Neither pass alone gets the full picture, but together they cover all constraints.

The two-pass greedy solution

Here is the complete solution in Python:

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

    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)

    return sum(candies)

Here is what each piece does:

1. Initialize candies = [1] * n. Every child starts with the minimum of 1 candy.
2. Left-to-right pass (indices 1 through n-1). If the current child has a higher rating than the child to its left, give it one more candy than that left child. This guarantees every uphill slope from left to right is satisfied.
3. Right-to-left pass (indices n-2 down to 0). If the current child has a higher rating than the child to its right, set its candies to the max of its current value and one more than the right child. The max is critical: it preserves any higher value from the left-to-right pass so that both constraints remain satisfied.
4. Return sum(candies).

Why taking the max is correct

After the left-to-right pass, every child satisfies the left constraint. But some children may violate the right constraint. The right-to-left pass fixes those violations. At each position, you might need to increase the candy count to satisfy the right constraint, but you must not decrease it below what the left constraint requires. That is exactly what max(candies[i], candies[i + 1] + 1) achieves.

If you used simple assignment instead of max in the second pass, you could break the left constraint you already established. The max operation is what makes the two passes composable.

Complexity analysis

You need to inspect every rating at least once, so O(n) time is optimal. The candies array is required to store the result, so O(n) space is necessary. There is a more complex O(1) space solution using slope counting, but the two-pass approach is cleaner and sufficient for interviews.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Two-pass greedy

The pattern of making two linear passes (forward and backward) to satisfy constraints from both directions:

result = [initial] * n

for i in range(1, n):
    if forward_condition(i):
        result[i] = update_forward(result[i - 1])

for i in range(n - 2, -1, -1):
    if backward_condition(i):
        result[i] = combine(result[i], update_backward(result[i + 1]))

In Candy, the forward condition checks if the rating increases left-to-right, and the backward condition checks if it increases right-to-left. In Product of Array Except Self, the forward pass accumulates prefix products and the backward pass accumulates suffix products. In Trapping Rain Water, the forward pass tracks the running max height from the left and the backward pass tracks it from the right. The skeleton is identical.

2. Forward-backward constraint satisfaction

The idea that when each element depends on neighbors in both directions, you can decouple the dependencies by processing each direction independently and merging. This avoids the circular dependency problem where fixing one neighbor breaks another. By processing left-to-right first, you establish a consistent state for one direction. Then the backward pass only needs to conditionally increase values, never decrease them.

This decoupling principle applies beyond arrays. Any time you have bidirectional dependencies, consider whether you can linearize them into two passes.

Edge cases

Before submitting, make sure your solution handles these:

• All same ratings [3, 3, 3, 3]: no child has a strictly higher rating than a neighbor, so every child gets 1 candy. Total = n.
• Strictly increasing [1, 2, 3, 4]: candies = [1, 2, 3, 4]. The left-to-right pass handles everything. The right-to-left pass makes no changes.
• Strictly decreasing [4, 3, 2, 1]: candies = [4, 3, 2, 1]. The left-to-right pass makes no changes. The right-to-left pass builds the staircase.
• V-shape [3, 1, 5]: the valley at index 1 gets 1 candy. Both neighbors get 2 each. Total = 5.
• W-shape [3, 1, 5, 1, 3]: two valleys, each with 1 candy. The peaks at indices 0, 2, and 4 get 2, 2, and 2. Total = 9.
• Single child [5]: just 1 candy. The loops do not execute.

The two-pass solution handles all of these without special-case logic.

Common mistakes

1. Using assignment instead of max in the second pass. Writing candies[i] = candies[i + 1] + 1 instead of candies[i] = max(candies[i], candies[i + 1] + 1) can break the left constraint. You must keep whichever value is larger.

2. Checking for not-equal instead of strictly greater. The problem says children with a higher rating than a neighbor get more candies. Equal ratings do not require more candies. Using != instead of > in the comparison leads to distributing more candies than necessary.

3. Forgetting to initialize all values to 1. Every child must get at least 1 candy. If you initialize to 0 and only set values during the passes, children at local maxima with equal neighbors on both sides could end up with 0.

4. Processing the second pass in the wrong direction. The right-to-left pass must go from n - 2 down to 0. Going left-to-right for both passes means the second pass is identical to the first and does not fix right-neighbor violations.

From understanding to recall

You have read the two-pass solution and it makes sense. Two loops, one max, done. But can you write it from scratch in an interview without looking at it?

The details matter: initializing candies to all 1s, starting the first loop at index 1 and the second at n - 2, using > not >=, and remembering the max in the second pass. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the two-pass greedy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "satisfy constraints from both neighbors" and the code flows out without hesitation.

The two-pass greedy pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Gas Station - Another greedy problem where a single-pass scan with resets replaces brute-force simulation
• Jump Game - Greedy farthest-reach tracking, another problem where greedy beats DP

CodeBricks breaks the candy LeetCode problem into its two-pass greedy and forward-backward constraint satisfaction building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a two-pass greedy question shows up in your interview, you do not think about it. You just write it.