Simple 2 pass Python code


  • 3
    W

    Never take some guess for granted!
    [1, 2, 2] is not 5, should be 4!

    Useq/Dseq stores one should have ?+1 candies since he/her has higher rating than left/right neighbor!

    class Solution:
        # @param {integer[]} ratings
        # @return {integer}
        def candy(self, ratings):
            n = len(ratings)
            Useq = [0 for i in range(n)]
            for i in xrange(1, n):
                if ratings[i]>ratings[i-1]:
                    Useq[i] = Useq[i-1]+1
            
            Dseq = [0 for i in range(n)]
            for i in xrange(n-2, -1, -1):  #from i = n-2, ... 1, 0 ## will not reach -1!!
                if ratings[i]>ratings[i+1]:
                    Dseq[i] = Dseq[i+1]+1
            
            candies = [max(Useq[i], Dseq[i])+1 for i in range(n)]
            return sum(candies)

Log in to reply
 

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