We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is a classic problem that can be solved by using the greedy approach.
Here's a possible algorithm:
Initialize an array of candies, all set to 1.
Traverse the ratings from left to right and update the candies array based on the rating of the current child and the child to the left.
Traverse the ratings from right to left and update the candies array based on the rating of the current child and the child to the right.
Compute and return the sum of the candies array.
Here's the detailed explanation:
First, we initialize an array of candies, all set to 1, since we need to give at least one candy to each child.
We traverse the ratings from left to right and update the candies array based on the rating of the current child and the child to the left. If the current child has a higher rating than the child to the left, we increase the number of candies for the current child by 1 compared to the child to the left.
We traverse the ratings from right to left and update the candies array based on the rating of the current child and the child to the right. If the current child has a higher rating than the child to the right, we increase the number of candies for the current child by 1 compared to the child to the right.
Finally, we compute and return the sum of the candies array.
Here's the sample code in Python:
defmin_candies(ratings):n=len(ratings)candies=[1]*n# Traverse from left to rightforiinrange(1,n):ifratings[i]>ratings[i-1]:candies[i]=candies[i-1]+1# Traverse from right to leftforiinrange(n-2,-1,-1):ifratings[i]>ratings[i+1]:candies[i]=max(candies[i],candies[i+1]+1)# Compute and return the sum of candiesreturnsum(candies)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Candies
You are viewing a single comment's thread. Return to all comments →
This is a classic problem that can be solved by using the greedy approach.
Here's a possible algorithm:
Here's the detailed explanation:
Here's the sample code in Python: