LeetCode 135: Candy

Problem Restatement

There are n children standing in a line.

Each child has a rating given by the integer array ratings.

We need to give candies to the children under two rules:

1. Each child must get at least one candy.
2. A child with a higher rating than an adjacent neighbor must get more candies than that neighbor.

Return the minimum total number of candies needed. The constraints include 1 <= n <= 2 * 10^4 and 0 <= ratings[i] <= 2 * 10^4.

Examples

Example 1:

ratings = [1, 0, 2]

The middle child has the lowest rating, so they can receive 1 candy.

The first child has a higher rating than the middle child, so they need more than 1.

The third child also has a higher rating than the middle child, so they need more than 1.

One minimum distribution is:

[2, 1, 2]

Total:

2 + 1 + 2 = 5

Output:

5

Example 2:

ratings = [1, 2, 2]

The second child has a higher rating than the first child, so the second child needs more candies than the first.

The third child has the same rating as the second child, so there is no strict requirement between them.

A minimum distribution is:

[1, 2, 1]

Output:

4

Input and Output

Function shape:

class Solution:
    def candy(self, ratings: list[int]) -> int:
        ...

First Thought: Adjust Until Valid

One simple idea is to start every child with one candy.

Then repeatedly scan the array and fix violations.

For example, if:

ratings[i] > ratings[i - 1]

but:

candies[i] <= candies[i - 1]

then increase candies[i].

This can work, but it may require many repeated updates. A change on the right can force another change farther left, especially in decreasing sequences.

Example:

ratings = [5, 4, 3, 2, 1]

The minimum candies are:

[5, 4, 3, 2, 1]

A repeated-fix approach can become inefficient.

We need a direct greedy method.

Key Insight

Each child has two possible constraints:

1. Constraint from the left neighbor.
2. Constraint from the right neighbor.

We can solve these separately.

Left-to-right pass:

If a child has a higher rating than the child on the left, they need one more candy than the left child.

if ratings[i] > ratings[i - 1]:
    candies[i] = candies[i - 1] + 1

Right-to-left pass:

If a child has a higher rating than the child on the right, they need one more candy than the right child.

if ratings[i] > ratings[i + 1]:
    candies[i] = max(candies[i], candies[i + 1] + 1)

The max matters because the child may already need more candies due to the left neighbor.

Why Two Passes Work

Consider:

ratings = [1, 2, 3, 2, 1]

A left-to-right pass gives:

[1, 2, 3, 1, 1]

This satisfies increasing slopes from the left.

But it fails on the right side:

3 > 2 > 1

The child with rating 2 at index 3 needs more candies than the child with rating 1 at index 4.

The right-to-left pass fixes that:

[1, 2, 3, 2, 1]

Now both directions are satisfied.

The first pass handles all rising edges from left to right.

The second pass handles all rising edges from right to left.

Taking the maximum keeps both constraints valid.

Algorithm

Initialize one candy for every child:

candies = [1] * n

Scan left to right.

For each i from 1 to n - 1:

if ratings[i] > ratings[i - 1]:
    candies[i] = candies[i - 1] + 1

Then scan right to left.

For each i from n - 2 down to 0:

if ratings[i] > ratings[i + 1]:
    candies[i] = max(candies[i], candies[i + 1] + 1)

Return:

sum(candies)

Correctness

Every child starts with one candy, so the first rule is satisfied.

After the left-to-right pass, for every adjacent pair where ratings[i] > ratings[i - 1], the algorithm sets candies[i] to at least candies[i - 1] + 1. Therefore, every higher-rating child satisfies the constraint against their left neighbor.

After the right-to-left pass, for every adjacent pair where ratings[i] > ratings[i + 1], the algorithm sets candies[i] to at least candies[i + 1] + 1. The max preserves any larger value already needed from the left-to-right pass.

Thus, after both passes, every adjacent higher-rating constraint is satisfied.

The assignment is minimal because each pass only raises a child’s candies when a local rule forces it. A child receives exactly the maximum amount required by its left-side increasing run and its right-side increasing run. Giving fewer candies to that child would violate at least one neighbor constraint.

Therefore, the sum of candies is the minimum total number of candies.

Complexity

Let n = len(ratings).

Implementation

class Solution:
    def candy(self, ratings: list[int]) -> int:
        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)

Code Explanation

We start with one candy per child:

candies = [1] * n

This satisfies the baseline rule.

The first pass handles the left neighbor:

for i in range(1, n):
    if ratings[i] > ratings[i - 1]:
        candies[i] = candies[i - 1] + 1

If the current child has a higher rating than the left child, they receive one more candy than the left child.

The second pass handles the right neighbor:

for i in range(n - 2, -1, -1):
    if ratings[i] > ratings[i + 1]:
        candies[i] = max(candies[i], candies[i + 1] + 1)

The max keeps the larger requirement.

Finally:

return sum(candies)

returns the minimum total.

Testing

def run_tests():
    s = Solution()

    assert s.candy([1, 0, 2]) == 5
    assert s.candy([1, 2, 2]) == 4
    assert s.candy([1]) == 1
    assert s.candy([1, 2, 3, 4]) == 10
    assert s.candy([4, 3, 2, 1]) == 10
    assert s.candy([1, 3, 4, 5, 2]) == 11
    assert s.candy([1, 2, 87, 87, 87, 2, 1]) == 13

    print("all tests passed")

run_tests()

Test meaning: