print array of previous smaller elements

Question

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 < i and A[j] < 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]>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]

Answer 1

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] >= 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.

Answer 2

Optimisation aside, there are some ways to make your code more pythonic

iterating

In Python, you almost never have to iterate over the index, so for i in range(len(arr)): can better be expressed for i, item in enumerate(arr):.

for j in range(i,-1,-1) can be for item_2 in arr[i::-1]

for: .. else:

thanks to the for-else clause, you can ditch the status-flag

generator

Instead of the new_stack = [] and new_stack.append, you can use yield to pass on a next item, and use list() in the end to turn it into a list.

def prev_smaller_generator(arr):
    for i, item in enumerate(arr):
        for item2 in arr[i::-1]:
            if item2 < item:
                yield item2
                break
        else:
            yield -1

assert list(prev_smaller_generator([34,35,27,42,5,28,39,20,28])) == [-1,34,-1,27,-1,5,28,5,20]
assert list(prev_smaller_generator([1])) == [-1]
assert list(prev_smaller_generator([1,4,5,6])) ==[-1,1,4,5]

Answer 3

@Alex answer solves the problem in only one pass over the data. However, you could also consider "cosmetic" improvements.

if name == main

Imagine you want to reuse this code. After writing more tests, you may not want to run the tests every time the script is loaded. The following will be run only if you call python myscript.py

if __name__ == "__main__":
    # execute only if run as a script
    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]

PEP 8

This is a set of convention to write python code. But there are several plugins to automatically follow these guidelines (I used Autopep 8 with VIM). More info about PEP8

def prev_smaller(arr):
    new_stack = []
    status = False
    for i in range(len(arr)):
        for j in range(i, -1, -1):
            if arr[i] > 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]