Python solution with detailed explanation

  • 0



    • Move from left to right. If ratings[i] > ratings[i-1], then candy[i] = candy[i-1]+1.
    • Move from right to left. If ratings[i] > ratings[i+1], then candy[i] = max(candy[i], candy[i+1]+1)
    • Proof - Sketch all 3 combinations with 2 ratings. The method gives right answer. Now add third rating and sketch all 6 combinations. Still get the right answer.
    class Solution(object):
        def candy(self, ratings):
            :type ratings: List[int]
            :rtype: int
            N = len(ratings)
            candy = [1]*N
            for i in range(1, N):
                if ratings[i] > ratings[i-1]:
                    candy[i] = candy[i-1] + 1
            for i in range(N-2, -1, -1):
                if ratings[i] > ratings[i+1]:
                    candy[i] = max(candy[i], candy[i+1]+1)
            return sum(candy)

Log in to reply

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