Candy

Candy is a classic greedy problem. The trick is realizing that one greedy sweep can only ever look in one direction — so you make two passes and combine them.

The slow way first

You could keep scanning the whole line, bumping any child who breaks a rule, and repeat until nothing changes. That loops an unknown number of times and is easily O(n²) in the worst case. We want a clean linear answer.

The question to ask: a single left-to-right scan can enforce the rule against the left neighbour — but what about the right neighbour? The fix is to run a second scan the other way.

The idea: two sweeps

Give everyone one candy to start. Then:

• Left → right: if ratings[i] > ratings[i-1], this child is rising from the left, so set candy[i] = candy[i-1] + 1.
• Right → left: if ratings[i] > ratings[i+1], this child is rising from the right, so set candy[i] = max(candy[i], candy[i+1] + 1).

The max is the key: the first sweep already gave this child a value to satisfy its left side, and we must not destroy that — we only raise it if the right side demands more.

Because each sweep only ever increases candies, combining them with max satisfies both rules at once, using the fewest candies possible.

Walk through it

Step through the animation. The first sweep moves i left to right, bumping 3 and 4 above their left neighbours. The second sweep moves right to left, taking the max so a child that already won its left comparison keeps that value. The candy label under each cell updates as we go; at the end we sum them.

Pseudocode

candies = [1, 1, ..., 1]              # one per child
for i from 1 to n-1:                  # left to right
    if ratings[i] > ratings[i-1]:
        candies[i] = candies[i-1] + 1
for i from n-2 down to 0:             # right to left
    if ratings[i] > ratings[i+1]:
        candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)

The Python solution

def candy(ratings):
    candies = [1] * len(ratings)
    for i in range(1, len(ratings)):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    for i in range(len(ratings) - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    return sum(candies)

• candies = [1] * len(ratings) gives every child the minimum of one candy.
• The first loop enforces the left rule: a rising child gets one more than the child on its left.
• The second loop walks backwards and enforces the right rule.
• Line 8 is the heart of it — max keeps whatever the left sweep already earned and only raises it if the right neighbour forces a bigger value.
• sum(candies) is the minimum total once both rules hold.

Complexity

Two linear passes plus an O(n) candies array. The max in the second pass is what lets two independent greedy sweeps cooperate without overwriting each other.

When this pattern shows up

Practice