Fair candies for the line
Hand out the fewest candies so that every child gets at least one and a child with a higher rating than a neighbour gets more, by fixing the left rule and the right rule in two passes. About 18 minutes.
Two rules, two directions
Children stand in a line with ratings. Every child gets at least one candy, and a child rated higher than a neighbour must get more candy than that neighbour. You want the fewest candies in total.
Each child is compared with both neighbours, which makes one pass awkward. Split the job: handle the rule about the left neighbour on its own, then the rule about the right neighbour on its own.
Take the larger demand
Start everyone at one candy. Pass from the left: if a child is rated above the one on their left, give one more than that child.
Then pass from the right: if a child is rated above the one on their right, they need at least one more than that child, so keep the larger of the current count and that requirement. Each count is raised only as far as needed, so the total is the smallest possible.
give = [1] * n give[i] = give[i - 1] + 1 # left to right
Start with 1, 1, 1, 1 candies. Left pass: child 1 is rated above child 0, so child 1 gets 2. The others are not above their left neighbour.
Ratings 1, 2, 2. What is the fewest candies in total?
- A4 (1, 2, 1)
- B5
- C3
Show the answer
4 (1, 2, 1). The middle child beats the first, so 2; the last is equal to the middle, so 1 is enough.
Fewest candies
Children stand in a line, and ratings[i] is the rating of child i. Every child must get at least one candy, and a child with a higher rating than an adjacent child must get more candies than that neighbour. Return the fewest candies needed in total.
ratings = [1, 0, 2] → 5
0 ≤ ratings.length ≤ 100,000 · 0 ≤ ratings[i] ≤ 100,000