Next Smaller Element

Problem

For each element of a list, find the next strictly smaller element to its right.

Use a monotonic increasing stack of indices; when a new value is smaller than the value at the index on top, it is the next smaller element for that index.

Return a list where result[i] is the next smaller value, or -1 when none exists.

Hint

Keep indices with increasing values; a smaller value arriving resolves every larger top.

Test cases

case 1

in: [[2,1,2,4,3]]

expected: [1,-1,-1,3,-1]

case 2

in: [[1,2,3,4]]

expected: [-1,-1,-1,-1]

case 3

in: [[4,3,2,1]]

expected: [3,2,1,-1]

case 4

in: [[]]

expected: []

Starter codePython

def next_smaller(nums):
    # Your code here
    pass

4 test cases · run your code against them in the editor