Given a line of children with ratings, the machine must distribute candies so every child gets at least one, and any child with a higher rating than a neighbor must get strictly more candy than that neighbor. It must return the minimum total candy count.
The key insight is that the rules decompose into two independent constraints: each child must beat the neighbor on the left, and each child must beat the neighbor on the right. No single pass can satisfy both, but each pass handles one direction cleanly, and taking the maximum of the two directional requirements satisfies both at once.
The approach runs in three steps. First, give every child one candy. Second, sweep left to right, giving each child one more candy than the left neighbor whenever its rating is higher. Third, sweep right to left, raising each child to at least one more than the right neighbor when its rating is higher, then sum the array. Time is O(n) and space is O(n).
The trickiest edge case is equal adjacent ratings: the rules only require more candy for strictly higher ratings, so [1,2,2] costs 4 candies, not 5 — the second child at rating 2 needs no extra candy for the equal right neighbor. Both passes must use strict comparisons, and long descending runs are handled entirely by the right-to-left sweep.
def candy(ratings):
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)