Python O(nlogn) time, O(n) space


  • 0
    D
    def candy(self, ratings):
        if ratings is None:
            return 0
        
        indexes = range(len(ratings))
        sorted_idx = [idx for (rtg, idx) in sorted(zip(ratings, indexes))]
        candies = [1 for x in range(len(ratings))]
        
        for idx in sorted_idx:
            left = ratings[idx] if idx == 0 else ratings[idx - 1]
            right = ratings[idx] if idx == len(ratings) - 1 else ratings[idx + 1]
            if ratings[idx] > left:
                candies[idx] = candies[idx - 1] + 1
            if ratings[idx] > right:
                candies[idx] = max(candies[idx + 1] + 1, candies[idx])
        
        return sum(candies)

Log in to reply
 

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