Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Candy
• Main tags: Array, Greedy

What the problem is really asking

There are children standing in a line. Each child has a rating, and the goal is to give out the fewest total candies while obeying two rules:

• every child gets at least one candy
• any child with a higher rating than an adjacent child must get more candies than that neighbor

The important detail is that the comparison is only between neighbors. A child does not need more candy than every lower-rated child, only more than the children immediately to the left and right when their rating is higher.

So the problem is really asking for the smallest assignment that satisfies all local left-right constraints.

The key insight

Each child may be constrained from two directions:

• from the left neighbor
• from the right neighbor

If ratings are increasing from left to right, candies also have to increase from left to right. A left-to-right pass captures exactly that requirement.

If ratings are decreasing from left to right, then the same requirement appears from the other direction. A right-to-left pass captures that requirement.

For each child, the final number of candies must satisfy both sides. That means the answer for each position is the larger of:

• the number needed to be valid compared with the left neighbor
• the number needed to be valid compared with the right neighbor

Taking the maximum is enough because the two adjacent rules are independent lower bounds on the same value.

How to derive the optimal solution

Start with the simplest valid assignment: give every child one candy.

Now scan from left to right. Whenever ratings[i] > ratings[i - 1], child i must receive more candy than child i - 1. The smallest way to make that true is:

candies[i] = candies[i - 1] + 1

After this pass, every increasing relationship from left to right is valid. But decreasing runs are still not fully handled. For example, in [5, 4, 3], the leftmost child should receive the most candies, and the left-to-right pass cannot discover that because each next rating is lower.

So scan from right to left. Whenever ratings[i] > ratings[i + 1], child i must receive more candy than child i + 1. The smallest value that satisfies the right side is:

candies[i + 1] + 1

But child i may already have enough candy from the left-to-right pass. To preserve both requirements, keep the larger value:

candies[i] = max(candies[i], candies[i + 1] + 1)

After both passes, all neighbor rules are satisfied, and the sum is minimal.

The complexity is:

• Time: O(n) because each child is processed twice
• Extra space: O(n) for the candy counts

There is also a one-pass slope-counting version that uses O(1) extra space. It is a useful follow-up, but the two-pass greedy method is usually the clearest production and interview solution because every stored value has an obvious meaning.

Why the greedy solution works

The left-to-right pass computes the minimum candies needed for every child to be valid against the child on the left.

The right-to-left pass computes the minimum candies needed for every child to be valid against the child on the right, while preserving the earlier left-side requirement.

For any child, these two requirements are just lower bounds. If the left side says the child needs at least 3 candies and the right side says the child needs at least 2, then 3 candies satisfies both. Giving 4 would be valid but not minimal.

That is why taking max(existing_candies, right_side_requirement) is the exact greedy choice. It gives each child the least amount possible while keeping both adjacent comparisons valid.

Python solution

from typing import List, Sequence


class Solution:
    def candy(self, ratings: List[int]) -> int:
        if not ratings:
            return 0

        candies = self._satisfy_left_neighbors(ratings)
        self._satisfy_right_neighbors(ratings, candies)
        return sum(candies)

    def _satisfy_left_neighbors(self, ratings: Sequence[int]) -> List[int]:
        candies = [1] * len(ratings)

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

        return candies

    def _satisfy_right_neighbors(
        self,
        ratings: Sequence[int],
        candies: List[int],
    ) -> None:
        for index in range(len(ratings) - 2, -1, -1):
            if ratings[index] <= ratings[index + 1]:
                continue

            # Keep the left-pass value if it is already large enough.
            candies[index] = max(candies[index], candies[index + 1] + 1)

Optimal one-pass O(1) space solution

The two-pass solution stores the candy count for every child. The optimal space solution avoids that array by counting the shape of the ratings as the scan moves left to right.

The key is that only three local shapes matter:

• an increasing run, such as [1, 2, 3]
• a decreasing run, such as [3, 2, 1]
• a flat break, such as [2, 2]

For an increasing run of edge length up, the candies are:

1 + 2 + ... + (up + 1)

For a decreasing run of edge length down, the candies are also triangular:

(down + 1) + down + ... + 1

For a mountain that rises and then falls, the peak child belongs to both the increasing side and the decreasing side. The peak only needs enough candy to satisfy the longer side, so the algorithm must avoid counting the peak twice.

State variables

The one-pass version keeps:

• total: total candies counted so far
• up: length of the current increasing slope
• down: length of the current decreasing slope
• peak: length of the most recent increasing slope before the current descent

Each slope length counts edges, not children. For example, ratings [1, 3, 5] have an increasing slope length of 2, and the required candies are [1, 2, 3].

How the update works

When ratings[i] > ratings[i - 1], the current child extends an increasing run. If up == 2, the current child needs 3 candies, so add up + 1 to the total.

When ratings[i] == ratings[i - 1], there is no neighbor constraint between these two children. The current child can receive one candy, and all slope state resets.

When ratings[i] < ratings[i - 1], the current child extends a decreasing run. A descending run discovered left to right is tricky because every new lower child may force earlier children in the run to be bumped up. Adding down + 1 accounts for:

• one candy for the current child
• one additional candy for each earlier child in the current descending tail

Then the peak correction decides whether to subtract one:

• if peak >= down, the old peak is already tall enough, so subtract 1 to avoid double-counting it
• if down > peak, the descent is longer than the rise, so the peak needs one more candy and no subtraction is made

That condition is the core of the O(1) solution.

Python solution

from typing import List


class Solution:
    def candy(self, ratings: List[int]) -> int:
        if not ratings:
            return 0

        total = 1
        up = 0
        down = 0
        peak = 0

        for index in range(1, len(ratings)):
            if ratings[index] > ratings[index - 1]:
                up += 1
                peak = up
                down = 0
                total += up + 1
            elif ratings[index] == ratings[index - 1]:
                up = 0
                down = 0
                peak = 0
                total += 1
            else:
                up = 0
                down += 1
                total += down + 1

                if peak >= down:
                    total -= 1

        return total

Why the peak correction matters

Consider [1, 2, 3, 2, 1].

The increasing part [1, 2, 3] contributes candies [1, 2, 3], so peak = 2 because the rise has two edges.

Then the decreasing part has length 2. The peak already has enough candy to be greater than both sides, so the algorithm subtracts one during each decreasing step where peak >= down. The final total is 9, matching [1, 2, 3, 2, 1].

Now consider [1, 2, 3, 2, 1, 0].

The descent length becomes 3, which is longer than the rise length 2. At that point, the original peak candy count of 3 is not enough; the peak must be bumped to 4. The algorithm handles that by not subtracting when down > peak, giving the final total 13, matching [1, 2, 4, 3, 2, 1].

The complexity is:

• Time: O(n) because each rating is processed once
• Extra space: O(1) because only counters are stored

Interview follow-ups

Can this be solved with O(1) extra space?

Yes. The one-pass slope-counting solution above is the optimal version: O(n) time and O(1) extra space.

In an interview, the tradeoff is clarity. The two-pass greedy method is easier to explain and prove. The one-pass method is more space efficient, but it requires careful handling of equal ratings, slope transitions, and the peak correction when a decreasing run follows an increasing run.

Why is a single left-to-right pass not enough?

A single left-to-right pass only enforces one direction of the rule. It handles cases where a child has a higher rating than the child on the left, but it misses the pressure created by a lower-rated child on the right.

For example, [3, 2, 1] would remain [1, 1, 1] after a left-to-right pass, even though the first child must get more than the second and the second must get more than the third. The right-to-left pass is what repairs those decreasing runs.

Why does the algorithm use max during the right-to-left pass?

The current candy count already satisfies the left-neighbor rule. The right-to-left pass introduces another possible requirement from the right neighbor.

If the right-side requirement is larger, the child needs more candy. If the existing left-pass value is larger, lowering it would break the left-side rule. Taking the maximum is therefore the smallest value that safely satisfies both directions.

How should equal ratings be handled?

Equal ratings do not create any ordering requirement. If two adjacent children have the same rating, neither child is required to receive more candy than the other.

That is why the code uses strict > comparisons. Equal-rated neighbors can both receive one candy unless another neighbor forces one of them higher. This detail is important because treating equality like an increase would overcount.

What edge cases are worth testing?

The most useful tests are the ones that exercise different slope patterns. A single child should need exactly one candy. All equal ratings should also stay flat because equality creates no ordering rule. Strictly increasing ratings should produce 1 + 2 + ... + n, while strictly decreasing ratings should produce the same total in reverse.

Peak and valley cases are especially important. A peak such as [1, 3, 4, 5, 2] checks that the highest-rated child receives enough candy for both sides. A valley such as [5, 3, 1, 3, 5] checks that the two passes can build outward in both directions without interfering with each other.

These tests confirm that the algorithm handles one-sided constraints, two-sided constraints, and equality without giving extra candy unnecessarily. They do not change the complexity: every case still runs in O(n) time, with O(n) extra space for the candy counts.

Practical takeaway

The clean way to solve Candy is to stop thinking about the whole line at once. Each child only has to satisfy local constraints with immediate neighbors.

One pass enforces the left constraint, another pass enforces the right constraint, and the maximum of those two needs gives the minimum valid candy count.