Candy

How it works

We can compute the result without storing candy counts for each child. The key insight is that ratings form a sequence of increasing and decreasing runs. For an increasing run of length k, we need 1+2+...+k extra candies above the base. For a decreasing run of length k, we also need 1+2+...+k extra candies. The peak between an increasing and decreasing run should belong to whichever run is longer.

Steps

1. Start with n candies (one per child as the base).
2. Iterate through the ratings, skipping equal adjacent ratings.
3. Count the length of each increasing run (consecutive ratings going up) and add the triangular number sum (1+2+...+inc) to the result.
4. Count the length of each decreasing run (consecutive ratings going down) and add its triangular sum to the result.
5. Subtract the minimum of the two run lengths since the peak was counted in both runs but should only be counted once (in the longer run).
6. Return the total.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Giving Extra Candy for Equal Ratings

Children with equal ratings do not need to have the same or related candy counts. Only strictly higher ratings require more candy than neighbors.

Only Considering One Direction

A single left-to-right pass handles the left neighbor constraint but ignores the right neighbor. The two-pass approach ensures both constraints are satisfied.

Not Taking Maximum in Second Pass

In the right-to-left pass, simply setting arr[i] = arr[i + 1] + 1 may violate the left neighbor constraint already established. You must take the maximum of the current value and the right constraint.

Off-by-One in Peak Handling (One-Pass Solution)

When counting increasing and decreasing sequences, the peak element gets counted in both. Forgetting to subtract min(inc, dec) results in overcounting candies.

from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        res = n

        i = 1
        while i < n:
            if ratings[i] == ratings[i - 1]:
                i += 1
                continue

            inc = 0
            while i < n and ratings[i] > ratings[i - 1]:
                inc += 1
                res += inc
                i += 1

            dec = 0
            while i < n and ratings[i] < ratings[i - 1]:
                dec += 1
                res += dec
                i += 1

            res -= min(inc, dec)

        return res

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int res = n;

        int i = 1;
        while (i < n) {
            if (ratings[i] == ratings[i - 1]) {
                i++;
                continue;
            }

            int inc = 0;
            while (i < n && ratings[i] > ratings[i - 1]) {
                inc++;
                res += inc;
                i++;
            }

            int dec = 0;
            while (i < n && ratings[i] < ratings[i - 1]) {
                dec++;
                res += dec;
                i++;
            }

            res -= min(inc, dec);
        }

        return res;
    }
};