LeetCode (Python): Candy

There are N children standing in a line. Each child is assigned a rating value.

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.

What is the minimum candies you must give?

Solution:

To obtain the number of candies per child, we pass the array in both directions. From left to right assures that if a child has higher rating than his left neighbor he will get more candies and from right to left for the opposite case. Afterwards we just have to sum the array. The running time is O(n).

class Solution:
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        candies = [1]
        for i in range(1,len(ratings)):
            if ratings[i]>ratings[i-1]:
                candies.append(candies[i-1]+1)
            else:
                candies.append(1)
        sum = candies[len(ratings)-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)
            sum += candies[i]
        return sum