Minimum Candies - Peaks and Vallies[Python]

Here’s the question on leetcode.

So we are given an array of ratings something like [1, 3, 2, 1, 2, 7, 5] and we need to handout as little candies as we can. So in my head(without any algorithm) the way I solved this was, well in 2 ways:

Going from left to right and changing the candies as required. It went like this:

['1']
[1, '2']
[1, 2, '1']
[1, 2, 1, '1'] -> [1, 2, '2', 1] ->[1, '3', 2, 1]
[1, 3, 2, 1, '2']
[1, 3, 2, 1, 2, '3']
[1, 3, 2, 1, 2, 3, '1']
Sum = 1 + 3 + 2 + 1 + 2 + 3 + 1 = 13

The problem which comes out pretty fast is that based on the rating you might increase the number of candies for a particular index but you might have to correct all the previous indexes as we see in the third line in the above example.

This is probably going to take O(N^2) Time

1. Starting from the smallest indexes and going outwards. This will take O(N) time.

Peaks and Valleys

The concept is to figure out when are we increasing/decreasing or finding out local minima and maxima. If we plot the above array we get a chart that looks like a mountain, hence the name peaks and valleys.

So finding these local minimums and expanding outwards feels a little involved.

Another way to solve this would be to go from left to right and update the number of candies for all the increasing ratings and similarly go right to left and do the same. We have to be careful about the peaks, where two rising sequences meet, we have to select the larger number of candies so that the peak is greater than both the sides.

def candy(ratings):
    candies = [1 for _ in ratings]

    for i in range(1, len(ratings)):
        if ratings[i] > ratings[i - 1]:
            candies[i] = max(candies[i], candies[i-1] + 1)

    for i in range(len(ratings) - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i+1] + 1)

    return sum(candies)