Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each child has a requirement coming from the left and another coming from the right. An increasing run forces candy counts to increase along that run. We can calculate the minimum required by each direction independently, then take the larger requirement at every position. Equal ratings impose no ordering between their candy counts.

Approach

Give every child one candy initially.
Scan left to right. If the current rating exceeds the previous rating, assign one more candy than the previous child; otherwise keep one.
Scan right to left. When the current rating exceeds the next rating, raise its count to at least the next child's count plus one. Use a maximum so this adjustment never violates the already-established left-side requirement.
Sum the counts. Each child receives exactly the larger of the two unavoidable directional lower bounds, so the allocation is valid and no valid allocation has a smaller total.

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

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

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

        return sum(res)

Complexity analysis

Let n = ratings.length. The two directional passes take O(n) time and the candy array takes O(n) auxiliary space.