Python solution with detailed explanation


  • 0
    G

    Solution

    Candy https://leetcode.com/problems/candy/

    • 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.
      http://stackoverflow.com/questions/11292913/candies-interviewstreet
    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.