Python - O(N) Time - O(N) Space - Explained
\n#Baraa\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        """\n        Good Example to check: \n        [8, 4, 2, 1, 3, 6, 7, 9, 5]\n 
```\n#Baraa\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        """\n        Good Example to check: \n        [8, 4, 2, 1, 3, 6, 7, 9, 5]\n        \n        STEP 1: we compare each number with number before it\n        if current number > number before it we have to increment our reward\n        i.e: res[i] = res[i - 1] + 1\n        \n        STEP 2: We compare same way but from end of the array to beggining of it\n        if current number > number after it we increment if and only if there is a need to increment\n        because maybe when we incremented in the first step we already gave more rewards for current number\n        this can be observed in the above example \n        """\n        \n        n = len(ratings)\n        res = [1] * (n)\n        for i in range(1, n):\n            if ratings[i] > ratings[i - 1] and res[i] <= res[i - 1]:\n                res[i] = res[i - 1] + 1\n        for i in range(n - 2, -1, -1):\n            if ratings[i] > ratings[i + 1] and res[i] <= res[i + 1]:\n                res[i] = res[i + 1] + 1\n        return sum(res)\n    \n\n\n```
['Greedy', 'Python']