The monotonic stack

A whole family of interview questions asks the same thing in different clothes: for every element, find the nearest element to its left (or right) that is smaller (or bigger). Next Greater Element, Largest Rectangle in Histogram and Trapping Rain Water are all members. One technique solves them all in O(n): the monotonic stack — a stack whose items are always kept in sorted order.

The question

We'll use one member of the family: previous smaller element. For each number, find the closest number to its left that is smaller, or -1 if there is none.

nums = [4, 5, 2, 10, 8]
ans  = [-1, 4, -1, 2, 2]

5's previous smaller is 4.  2 has nothing smaller to its left: -1.
10's is 2.  8's is 2 (10 is closer, but not smaller).