Python O(n), running time ~80ms, with explainations


  • 0
    C
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        if not ratings:
            return 0
        
        sumCandies = 1 # keeps track of the sum
        numDesc = 1    # tracks descending ratings
        prevNumCandies = 1  # tracks numCandies in ascending ratings
        cushion = 0    
        
        """
        When sequence ascends, prevNumCandies ++, add it to sum.
        When sequence descends, immediately lower num candies given to the current child to 1. 
        If previous child already has 1 candy, add 1 to all numbers in descending sequence, and apply the cushion.
        Cushion is applied only 1st element in the descending queue. 
        """
        for idx in range(1, len(ratings)):
            if ratings[idx] > ratings[idx - 1]:
                prevNumCandies += 1
                sumCandies += prevNumCandies
                numDesc = 1
            elif ratings[idx] == ratings[idx - 1]:
                prevNumCandies = 1
                numDesc = 1
                sumCandies += 1
                cushion = 0
            else:
                numDesc += 1
                if prevNumCandies == 1:
                    sumCandies += numDesc
                    if cushion:
                        cushion -= 1
                        sumCandies -= 1
                else:
                    cushion = prevNumCandies - 2
                    prevNumCandies = 1
                    sumCandies += 1
        return sumCandies

Log in to reply
 

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