[Array] LeetCode 135. Candy

Solution Greedy O(n)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n

        for i in range(1,n):
            if ratings[i] > ratings[i-1]:
                candies[i] = candies[i-1] + 1

        for i in range(n-2,-1,-1):
            if ratings[i] > ratings[i+1]:
                candies[i] = max(candies[i+1] + 1, candies[i])

        return sum(candies)

This problem could be simply solved by iterating the for loop two times for ascending and descending order.

1. Ascending order checks children with a higher rating get more candies than its left neighbor.
2. Descending order checks children with a higher rating get more candies than its right neighbor.