Kids stand in a row, and kid i has score ratings[i]. You hand out candies so that:
- every kid gets at least one candy, and
- a kid whose score is strictly higher than a neighbour's gets strictly more candies than that neighbour. Equal neighbours have no constraint between them.
Write min_candies(ratings: list[int]) -> int, the smallest total that satisfies both rules. ratings may be empty (answer 0) and may hold up to 2 * 10**5 values, including negatives.
min_candies([3, 1, 2]) # 5 -> [2, 1, 2]
min_candies([1, 2, 2]) # 4 -> [1, 2, 1]
min_candies([1, 3, 4, 5, 2]) # 11 -> [1, 2, 3, 4, 1]
Aim for O(n). Repeatedly fixing violations until nothing changes gives the right answer, but it is quadratic on long decreasing runs.
Discussion (not tested)
- Argue that your answer is the minimum, not just valid.
- Walk through a single kid, all-equal scores, strictly increasing, strictly decreasing, and a peak.
- Can you do it in O(1) extra space?
Show hint
each kid is constrained from two sides: by the rising run that reaches them from the left, and by the one that reaches them from the right. Work out each side's requirement on its own, then combine them.