Python O(N) solution with O(2N) space complexity


#1
class Solution:
# @param A : list of integers
# @return an integer
def candy(self, A):
    n = len(A)-1
    l, r = [1]*(n+1), [1]*(n+1)
    count = 0
    
    for i in range(n):
        if A[i+1] > A[i]:       #iterating left to right if right > left add left + 1 to right
            l[i+1] = l[i] + 1
        if A[n-1-i] > A[n-i]:   #iterating right to left if left > right add right + 1 to left
            r[n-1-i] = r[n-i]+1
    
    for i in range(len(l)):
        count += max(l[i], r[i])
        
    return count