n children stand in a row, each with an integer rating. You hand out candies under two rules: every child gets at least one candy, and any child whose rating is strictly higher than an adjacent neighbor (left or right) must receive strictly more candies than that neighbor.
Return the minimum total number of candies you must hand out.
Line 1: an integer n, the number of children.
Line 2: n space-separated integers, the ratings in row order (present whenever n >= 1).
A single integer: the minimum total candies satisfying both rules.
Example 1
Input
3 1 0 2
Expected
5
Explanation
Give candies 2, 1, 2. The middle child rates lowest so gets 1; each neighbor rates higher so gets 2. Total 5, the minimum.
Example 2
Input
3 1 2 2
Expected
4
Explanation
Give 1, 2, 1. The second child outranks the first so needs more (2 vs 1); the third ties the second, so it may stay at 1. Total 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →