Previous Smaller Element

For each position, find the nearest index to the left with a strictly smaller value.

arrays stack monotonic-stack indices

Given a list of integers `arr`, return a new list `result` of the same length where for each index `i` (from 0 to n-1), `result[i]` is the index of the **nearest** index `j` such that `j < i` and `arr[j] < arr[i]`. If no such index exists, use `-1`. "Nearest" means the largest `j` that satisfies the condition. Implement the function `previous_smaller(arr: list[int]) -> list[int]`.

Constraints

The input list will have at most 10^5 integers (values can be negative, zero, or positive). The list may be empty. If the list is empty, return an empty list. Time complexity O(n) is expected.

Example

>>> previous_smaller([3, 1, 5, 7, 4, 2])
[-1, -1, 1, 2, 1, 1]
>>> previous_smaller([1, 2, 3, 4])
[-1, 0, 1, 2]
>>> previous_smaller([])
[]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about maintaining a stack of indices that are potential candidates.

When processing a new element, pop from the stack until you find an index with a value smaller than the current element.

The top of the stack after popping is the nearest previous smaller element's index.

Remember to push the current index onto the stack for future elements.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.