print array of previous smaller elements I am solving interview question from here.


  Problem : Given an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.
  
  More formally, G[i] for an element A[i] = an element A[j] such that 
      j is maximum possible and j &lt; i and A[j] &lt; A[i].
  Elements for which no smaller element exist, consider next smaller element as -1.
  
  Example: Input : A : [4, 5, 2, 10, 8] Return : [-1, 4, -1, 2, 2]


How can I optimise my solution:

def prev_smaller(arr):
    new_stack = []
    status = False
    for i in range(len(arr)):
        for j in range(i,-1,-1):
            if arr[i]&gt;arr[j]:
                status = True
                new_stack.append(arr[j])
                break
        if not status:
            new_stack.append(-1)
        status = False
    return new_stack

assert prev_smaller([34,35,27,42,5,28,39,20,28]) == [-1,34,-1,27,-1,5,28,5,20]
assert prev_smaller([1]) == [-1]
assert prev_smaller([1,4,5,6]) ==[-1,1,4,5]
This can be done in a single pass over input list with a stack to keep track of previous smaller elements. Note that the stack will have a sub-sequence that is sorted at any given point.

def FastSolve(v):
  res = []
  s = [-1]
  for x in v:
    while s[-1] &gt;= x:
      s.pop()
    res.append(s[-1])
    s.append(x)
  return res


Note that this exact question has been asked before here and a very similar variation (next smaller instead of last) here - the latter question has an excellent detailed explanation of the O(n) solution and code examples.