• + 2 comments

    This is a classic problem that can be solved by using the greedy approach.

    Here's a possible algorithm:

    1. Initialize an array of candies, all set to 1.
    2. 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.
    3. 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.
    4. Compute and return the sum of the candies array.

    Here's the detailed explanation:

    1. First, we initialize an array of candies, all set to 1, since we need to give at least one candy to each child.
    2. 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.
    3. 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.
    4. Finally, we compute and return the sum of the candies array.

    Here's the sample code in Python:

    def min_candies(ratings):
        n = len(ratings)
        candies = [1] * n
    
        # Traverse from left to right
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
    
        # Traverse from right to left
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
    
        # Compute and return the sum of candies
        return sum(candies)