Python O(n) solution without using stack


#1
def prevSmaller(self, A):
    ans = []
    smallest = 0
    for i in range(len(A)):
        if A[i] > A[smallest]:
            for j in range(i-1, smallest - 1, -1):
                if A[j] < A[i]:
                    ans.append(A[j])
                    break
        else:
            ans.append(-1)
            smallest = i
    return ans