Candy (LeetCode 135)

The problem

Children stand in a line, each with a rating. Give out candies so that:

• every child gets at least one candy, and
• a child with a higher rating than a neighbour gets more candies than that neighbour.

Return the minimum total number of candies.

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

Give [2, 1, 2]. The middle child has the lowest rating and gets 1; each end child beats the middle, so each gets 2.

How to think about it

Start with brute force. Give everyone 1 candy. Then repeatedly scan the line, and whenever a child beats a neighbour but doesn’t have more candy, bump them up. Repeat until nothing changes. A long decreasing run makes this take O(n) passes, so O(n²) total.

The key insight: split the rule in two. “More than a higher-rated neighbour” is really two independent rules: one about the left neighbour and one about the right neighbour. Each is easy on its own:

• Left rule: scan left to right. If ratings[i] > ratings[i-1], set c[i] = c[i-1] + 1. Each child now has the fewest candies that satisfy the left rule.
• Right rule: scan right to left. If ratings[i] > ratings[i+1], child i needs at least c[i+1] + 1.

Combine with max. In the second pass, set c[i] = max(c[i], c[i+1] + 1). Taking the max keeps the left rule satisfied while meeting the right rule. Each value is the smallest that meets both lower bounds, so the total is minimal.

Which pattern is this? Greedy with two directional sweeps. The tell is a constraint between each element and both neighbours: handle each direction in its own pass, then merge.

Approach

1. Give every child 1 candy: c = [1] * n.
2. Left to right, for i from 1: if ratings[i] > ratings[i-1], set c[i] = c[i-1] + 1.
3. Right to left, for i from n - 2 down to 0: if ratings[i] > ratings[i+1], set c[i] = max(c[i], c[i+1] + 1).
4. Return sum(c).

Solution

def candy(ratings):
    n = len(ratings); c = [1] * n
    for i in range(1, n):                    # left rule: beat the left neighbour
        if ratings[i] > ratings[i-1]:
            c[i] = c[i-1] + 1
    for i in range(n - 2, -1, -1):           # right rule, without breaking the left rule
        if ratings[i] > ratings[i+1]:
            c[i] = max(c[i], c[i+1] + 1)
    return sum(c)
# candy([1,0,2]) -> 5

Dry run

On ratings = [1, 0, 2], starting from c = [1, 1, 1]:

The total is 5. For a peak like [1, 3, 4, 5, 2], the left pass gives [1, 2, 3, 4, 1] and the right pass keeps it (the max protects the 4), total 11.

Complexity

• Time: O(n). Two linear passes and a sum.
• Space: O(n). The candy array. A one-pass O(1)-space version exists (counting up and down slopes), but it is far easier to get wrong in an interview.

Edge cases and pitfalls

• One child gets 1 candy.
• Equal neighbours have no constraint between them. [1, 2, 2] gives [1, 2, 1], total 4.
• Overwriting instead of max in the second pass breaks peaks: the 4 in [1, 3, 4, 5, 2] would drop to 2.
• One pass only handles just one neighbour; decreasing runs come out wrong.
• Sorting by rating and assigning in that order also works, but it is O(n log n) and messier.

Related problems

• Trapping Rain Water (LeetCode 42): another answer built from a left-to-right and a right-to-left pass.
• Product of Array Except Self (LeetCode 238): prefix and suffix sweeps combined per index.
• Assign Cookies (LeetCode 455): a gentler greedy about handing things to children.