Share my two python solutions both O(n) time, O(n) and O(1) extra space


  • 2
    Y

    The first one is O(n) space, but very concise. The idea is to find the mininum candies for each child considering only left or right neighbors.

    class Solution:
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        candies = [1] * len(ratings)
        for i in xrange(len(ratings) - 1):
            if ratings[i + 1] > ratings[i]:
                candies[i + 1] = max(candies[i + 1], candies[i] + 1)
                
            j = -i - 1
            if ratings[j - 1] > ratings[j]: 
                candies[j - 1] = max(candies[j - 1], candies[j] + 1)
        
        return sum(candies)
    

    The second one is O(1) space, a little bit more complicated. The idea is during one scan find all up-then-down hills in the ratings.

    class Solution:
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        if len(ratings) == 1:    return 1
    
        def count_hill(up, down):
            x, y = max(up, down), min(up, down) - 1
            return (x * (x + 1) + y * (y + 1)) / 2
            
        up = down = extra = 0
        direction = ratings[1] - ratings[0]
    
        for i in xrange(1, len(ratings)):
            if direction > 0:  up += 1      # one more on the uphill side
            if direction < 0:  down += 1    # one more on the downhill side
    
            if i == len(ratings) - 1:   break
    
            dr = ratings[i + 1] - ratings[i]
            if dr == 0 or direction < 0 < dr:   # count extra for a hill
                extra += count_hill(up, down)
                up = down = 0
            direction = dr
    
        return extra + count_hill(up, down) + len(ratings)

  • 0

    @yintaosong
    I know it is an old thread but just in case anyone see and understand the second solution:
    Could you please explain how the hill counting work?

    My vague understanding is that to count a hill, it is essentially calculating the area under it ? (x * (x + 1) + y * (y + 1)) / 2 seems to be the area of two triangles but not very sure about it.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.