# 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:

```python
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:

```python
[2, 1, 2]
```

Total:

```python
2 + 1 + 2 = 5
```

Output:

```python
5
```

Example 2:

```python
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:

```python
[1, 2, 1]
```

Output:

```python
4
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `ratings: list[int]` |
| Output | Minimum total candies |
| Rule 1 | Every child gets at least one candy |
| Rule 2 | Higher rating than a neighbor means more candies than that neighbor |
| Important detail | Equal ratings do not require equal candies |

Function shape:

```python
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:

```python
ratings[i] > ratings[i - 1]
```

but:

```python
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:

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

The minimum candies are:

```python
[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.

```python
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.

```python
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:

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

A left-to-right pass gives:

```python
[1, 2, 3, 1, 1]
```

This satisfies increasing slopes from the left.

But it fails on the right side:

```text
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:

```python
[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:

```python
candies = [1] * n
```

Scan left to right.

For each `i` from `1` to `n - 1`:

```python
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`:

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

Return:

```python
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)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two linear passes |
| Space | `O(n)` | One candies array |

## Implementation

```python
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:

```python
candies = [1] * n
```

This satisfies the baseline rule.

The first pass handles the left neighbor:

```python
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:

```python
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:

```python
return sum(candies)
```

returns the minimum total.

## Testing

```python
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:

| Test | Why |
|---|---|
| `[1, 0, 2]` | Valley shape |
| `[1, 2, 2]` | Equal ratings create no strict constraint |
| `[1]` | Single child |
| Increasing ratings | Left-to-right pass dominates |
| Decreasing ratings | Right-to-left pass dominates |
| Peak near the end | Needs both passes |
| Plateau in the middle | Equal ratings should not force extra candies |