Problem
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Testcases
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.
Initial Result
Time spent: 13 min
Fail. Passed half of all testcases.
Initial Approach
I did a simple pivot-based solution where I would use an arbitrary occurence of the lowest value (or “valley”) in the array to determine the amounts needed to increase by propagating outwards in each direction to satisfy each neighbor (and their neighbors, etc).
What I Missed
Running forward and backward through the array each tell us partial information about the candies we must give out to satisfy each child. This was clear to me, but what I didn’t see is that these two passes put together actually tells us our total count of candies needed but slightly overcounted due to the overlapping segment of these two sums.
Approach to the Solution
Recognize that passing forward and backward and incrementing for each increasing segment (for that direction) allows you to see all the candies needed for the children (on top of the 1 that they each have to begin with). This means we can add 1 candy to the 1st “step up” in an increasing segment, 2 to the next one, 3 to the next, and so on. This means we have a height that increases by 1 within an increasing segment and that each iteration also adds that whole height to the output (number of candies needed). When we’re done, we can think of this as 2 triangles, one for increasing and one for decreasing. They must overlap at a point that is their maximum heights respectively. At this point, we can remove the minimum of the two heights to adjust for the amount that has already been counted (remember this is not a point on a graph or the extrema of a continuous function - it’s a child (!) and therefore has one discrete minimum amount of candies). After subtracting, we return our result.
Key Takeaways
Consider patterns of increasing/decreasing numbers in problems that rely on order.