LC-0135 Hard LeetCode

135. Candy

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 45% Topics: Array, Greedy

Reading material

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    # @param ratings, a list of integer
    # @return an integer
    def candy(self, ratings):
        candies = [1 for _ in xrange(len(ratings))]
        for i in xrange(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        for i in reversed(xrange(1, len(ratings))):
            if ratings[i - 1] > ratings[i] and candies[i - 1] <= candies[i]:
                candies[i - 1] = candies[i] + 1

        return sum(candies)

Solution from kamyu104/LeetCode-Solutions · MIT