Hand out the fewest candies so higher-rated kids beat their neighbours. Sweep left to right, then right to left, keeping the larger count.
▼The problem
LeetCode 135 (Hard). n children stand in a line, each with a rating. Give out candies so that every child gets at least one, and a child with a higher rating than a neighbour gets more candies than that neighbour. Return the minimum number of candies.
Examples (LeetCode's): [1,0,2] → 5 (2, 1, 2) and [1,2,2] → 4 (1, 2, 1: equal ratings need no relation).
The solution
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)Transcript
Candy. Children stand in a line, each with a rating. Everyone gets at least one candy, and a child rated higher than a neighbor gets more than that neighbor. Return the minimum total.
Take ratings one, zero, two. The middle gets one; both neighbors outrank her, so they get two: five candies. For one, two, two: one, two, one, so four. Equal ratings don't need equal candy.
The slow way: give everyone one, then sweep the line, bumping any child who breaks the rule, until nothing changes. A falling run is fixed one step per sweep: order n squared.
The trick is two greedy passes. Left to right, a child who outranks her left neighbor gets one more than her. Then right to left, a child who outranks her right neighbor needs one more than that, so she keeps the larger count.
In code, start everyone at one. Left pass: if ratings i beats the one before, it gets the previous plus one. Right pass: if it beats the one after, take the max with the next plus one. Return the sum.
Now one, three, five, four, two, one. Left pass: one, two, three, then the drop resets: one, one, one. Right pass: two beats one, so two. Four beats two: three. Five beats four: the left pass said three, the right needs four, so four. Total: thirteen.
Two passes: order n time, and order n space for the candies. A slope-counting version needs only order one space.
Count up, count down, keep the max. That's Candy.