Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

 

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

 

Constraints:

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

SOLUTION:

class Solution:
    def getNum(self, graph, i, res):
        if res[i] != -1:
            return res[i]
        mval = 0
        for j in graph[i]:
            curr = self.getNum(graph, j, res)
            mval = max(mval, curr)
        res[i] = 1 + mval
        return 1 + mval
    
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        graph = {}
        for i in range(n):
            graph[i] = []
            l = float('inf')
            r = float('inf')
            if i > 0:
                l = ratings[i - 1]
            if i < n - 1:
                r = ratings[i + 1]
            if ratings[i] > l:
                graph[i].append(i - 1)
            if ratings[i] > r:
                graph[i].append(i + 1)
        res = [-1] * n
        for i in range(n):
            self.getNum(graph, i, res)
        return sum(res)