DEV Community

Avin Sharma
Avin Sharma

Posted on • Originally published at avinsharma.com on

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)

AWS GenAI LIVE image

Real challenges. Real solutions. Real talk.

From technical discussions to philosophical debates, AWS and AWS Partners examine the impact and evolution of gen AI.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay