Monotonic Stack

A monotonic stack is an ordinary stack with one house rule: before you push a new element, you first pop off anything already on the stack that breaks the order you want to keep. The result is a stack whose values are always increasing (or always decreasing) from bottom to top. That one rule is enough to answer a whole family of questions of the form "for each element, what's the next thing bigger than it?" in a single pass instead of the obvious nested-loop scan.

The reason to care: the naive way to find, for every element, the next larger element to its right is to look forward from each position, which is $O(n^2)$. A monotonic stack does the same job in $O(n)$ because each element is pushed once and popped once, and never touched again.

The core idea

Walk left to right. Keep on the stack the indices of elements that are still "waiting" for their answer. When the current element is bigger than the value at the top of the stack, that top element has just found its next-greater element, so pop it and record the answer. Keep popping while the rule is violated, then push the current index. Whatever is left on the stack at the end never found a larger element.

Worked example: next greater element

Take the array [2, 1, 5, 3]. For each entry we want the next value to its right that is strictly larger, or -1 if there is none. We keep a decreasing stack of indices (values large at the bottom). Here is every step; the stack column shows the values sitting on it:

Step	Value	Action	Stack (values)	Answers set
i=0	2	push	[2]	—
i=1	1	1 < 2, push	[2, 1]	—
i=2	5	5 > 1 pop→ans[1]=5; 5 > 2 pop→ans[0]=5; push	[5]	ans[1]=5, ans[0]=5
i=3	3	3 < 5, push	[5, 3]	—
end	—	leftovers get -1	—	ans[2]=-1, ans[3]=-1

Final answer: [5, 5, -1, -1]. Notice that 5 resolved two waiting elements at once when it arrived, and the pops it triggered are exactly the elements it "dominated."

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []                      # holds indices, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x    # x is the answer for the popped index
        stack.append(i)
    return ans

Choosing the direction

The whole trick is picking increasing vs. decreasing correctly. A useful rule of thumb:

• Want the next greater element → maintain a decreasing stack (pop when the incoming value is larger).
• Want the next smaller element → maintain an increasing stack (pop when the incoming value is smaller).
• Scanning right to left flips "next" to "previous."

Where it shows up in quant-dev interviews

This pattern is a favorite because it looks like it must be quadratic and isn't. The classic finance-flavored version is the stock span problem: for each day, how many consecutive prior days had a price less than or equal to today's? That is a "previous greater" scan straight out of the playbook. Largest rectangle in a histogram, the trapping-rain-water problem, and "sliding window maximum" (via a monotonic deque) are the other three you should have seen once. All four reduce to the same push-once, pop-once discipline.

If you can state the amortized $O(n)$ argument, pick the direction from the wording, and handle the leftover elements on the stack at the end, you have the whole pattern. It pairs naturally with the The Sliding Window Technique and with the FIFO-per-price-level logic inside an Order Book Data Structure.