Write prev_smaller(nums: list[int]) -> list[int].
For each index i, find the closest index j < i with nums[j] < nums[i] (strictly smaller) and put j in the answer, or -1 if no earlier value is smaller.
prev_smaller([3, 1, 4, 1, 5]) # [-1, -1, 1, -1, 3]
# 3: nothing before it -> -1
# 1: 3 is not smaller -> -1
# 4: nums[1] = 1 is smaller -> 1
# 1: equal is not smaller -> -1
# 5: nums[3] = 1 is the closest -> 3
prev_smaller([2, 5, 7]) # [-1, 0, 1]
Constraints: up to 2 * 10^5 values, possibly negative or repeated. Walking left from every index is O(n²) on inputs like a decreasing array, so it fails the large test. This is the building block behind "largest rectangle in a histogram".
Show hint
keep a stack of indexes whose values increase from bottom to top; for each new value, pop everything >= it (those can never be the answer for anyone later), then the top of the stack (if any) is the answer, and push the current index.