How to Find the Previous Smaller Element in Python

Use a monotonic stack to find the nearest smaller element to the left of each item in a list, returning -1 when none exists.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 15 views 0 copies

monotonic stack stack arrays algorithm

Python code

24 lines

Python 3.9+

from collections import deque

def previous_smaller_elements(arr):
    stack = deque()
    result = [-1] * len(arr)

    for i in range(len(arr)):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        if stack:
            result[i] = arr[stack[-1]]
        stack.append(i)

    return result

if __name__ == "__main__":
    test_cases = [
        [4, 5, 2, 10, 8],
        [3, 3, 3, 3],
        [1, 2, 3, 4, 5],
        [5, 4, 3, 2, 1]
    ]
    for nums in test_cases:
        print(f"arr={nums} -> previous_smaller={previous_smaller_elements(nums)}")

Output

stdout

arr=[4, 5, 2, 10, 8] -> previous_smaller=[-1, 4, -1, 2, 2]
arr=[3, 3, 3, 3] -> previous_smaller=[-1, -1, -1, -1]
arr=[1, 2, 3, 4, 5] -> previous_smaller=[-1, 1, 2, 3, 4]
arr=[5, 4, 3, 2, 1] -> previous_smaller=[-1, -1, -1, -1, -1]

How it works

The stack stores indices of elements that could still be the previous smaller for upcoming items. Because the while loop pops elements that are greater than or equal to the current value, the stack stays strictly increasing in value from bottom to top. When the loop ends, the index on top of the stack (if any) points to the closest smaller element to the left, so we read its value. Appending the current index after each check keeps the invariant for the next iteration. This runs in O(n) time because every index is pushed and popped at most once.

Common mistakes

Using stack values instead of indices — you need indices to compare positions correctly.
Forgetting to pop while the top is greater than or equal, which breaks the strictly increasing order.
Setting result to 0 instead of -1 when no smaller element exists.
Not initializing result with -1, leaving a wrong placeholder for early elements.

Variations

Use a plain list as a stack (append/pop) instead of deque.
Modify the condition to find the previous greater or equal element by changing the comparison.

Real-world use cases

Computing the width of histogram bars for the largest rectangle area problem.
Finding the nearest lower price before a timestamp in financial market order data.
Preprocessing temperature or stock arrays to answer range queries about local minima.

How to Find the Previous Smaller Element in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes