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]

• Peter Badida: Please don't use for-else, it's ugly and this Python feature makes porting between languages less obvious.
• Maarten Fabré: in cases like this, it allows for very concise code, that easily expresses what you mean

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]

• Maarten Fabré: I don't like your linebreak on assert prev_smaller([34, 35, 27, 42, 5, 28, 39, 20, 28] new_line ) == [-1, 34, -1, 27, -1, 5, 28, 5, 20]. Personally, I would either replace the long array with a variable, or so prev_smaller( new_line + indent [34, 35, 27, 42, 5, 28, 39, 20, 28] new_line ) == [-1, 34, -1, 27, -1, 5, 28, 5, 20]