Monotonic stack — invariant is the trick

First, the words — what "monotonic" even means

Before any code, let us pin down the vocabulary, because the whole technique is named after one word. Monotonic is just a fancy way of saying "always moving in one direction, never doubling back." A sequence is monotonically increasing if every number is at least as big as the one before it (5, 5, 8, 12, 12, 30), and monotonically decreasing if every number is at least as small (30, 30, 12, 8, 5). The opposite of monotonic is a sequence that goes up and down like a roller coaster.

A stack is the last-in-first-out pile from the on-ramp above: you can only add to the top (push) and remove from the top (pop), like a stack of plates. A monotonic stack, then, is simply a stack that we force to stay sorted from bottom to top — we never let a value sit on the stack if the rules say it has been "answered" and should leave. The magic is that maintaining that one rule, on every push, quietly solves a whole family of problems.

The problem it was born to solve: "next greater element"

The classic motivating task is the next greater element (NGE). Given an array, for each position you want the first value to its right that is strictly larger than it. For example, in [2, 1, 4, 3] the next greater of 2 is 4, the next greater of 1 is 4, the next greater of 4 is "none" (nothing bigger to its right), and the next greater of 3 is also "none". The obvious solution is a double loop: for each element, scan right until you find something bigger. That is O(n²) — for an array of n items you do roughly n scans of length n. A monotonic stack does the same job in a single pass.

Here is the core idea. We walk left to right and keep a stack of elements that are still waiting for their next-greater answer. To do NGE we keep the stack monotonically decreasing (big at the bottom, small at the top). When the new element is bigger than the value on top of the stack, that new element is the answer that top value was waiting for — so we pop it, record the answer, and keep popping until the top is bigger than the newcomer again. Then we push the newcomer and move on.

A fully traced dry-run

Let us run the next-greater-element algorithm on nums = [2, 1, 4, 3] by hand. We store indices on the stack (so we can write the answer into the right slot), but to keep it readable the trace below shows the values at those indices. We start with an empty stack and an answer array [-1, -1, -1, -1] (the -1 means "no greater element found yet"). The invariant — stack values strictly decreasing top-to-bottom — holds at every line.

# nums = [2, 1, 4, 3]   stack shown bottom -> top, by VALUE
#
# i=0, val=2: stack empty, nothing to pop. push 2.
#            stack = [2]            ans = [-1,-1,-1,-1]
#
# i=1, val=1: top is 2, and 2 > 1, so 1 does NOT pop it
#            (1 is not anyone's next-greater). push 1.
#            stack = [2, 1]         ans = [-1,-1,-1,-1]
#
# i=2, val=4: top is 1, and 4 > 1 -> 4 is 1's next greater.
#            pop 1, set ans at 1's index = 4.
#            now top is 2, and 4 > 2 -> 4 is 2's next greater.
#            pop 2, set ans at 2's index = 4.
#            stack now empty. push 4.
#            stack = [4]            ans = [4, 4,-1,-1]
#
# i=3, val=3: top is 4, and 4 > 3, so 3 does NOT pop it. push 3.
#            stack = [4, 3]         ans = [4, 4,-1,-1]
#
# end of array: whatever is left on the stack (4 and 3) never
# found anything bigger to the right, so they keep ans = -1.
# FINAL ans = [4, 4, -1, -1]

Read those answers back against the array: 2 → 4, 1 → 4, 4 → none, 3 → none. Exactly right, in one left-to-right sweep. Notice that at i=2 the new value 4 popped two elements at once — that is the algorithm resolving a backlog of waiting queries in a single move, and it is the heart of why this is fast.

Why it is amortized O(n), not O(n²)

At a glance the code looks like nested loops: an outer for over the array and an inner while that pops. Nested loops usually scream O(n²). But here the inner loop is special. Look at the lifetime of any single element: it gets pushed onto the stack exactly once, and it gets popped off at most once. Once popped, it never comes back. So across the entire run, the total number of pop operations can be at most n, no matter how the values are arranged.

That kind of accounting is called amortized analysis: instead of asking "what is the worst cost of one step?", you ask "what is the total cost spread across all steps?" One particular step (like i=2 above) might pop several elements and feel expensive, but it can only do so because earlier cheap steps pushed those elements without popping anything. The expensive steps and the cheap steps share a single budget of n pushes and n pops. Total work = n pushes + n pops + n iterations = O(n) — linear, even though no individual loop iteration is bounded by a constant. We say each element is processed in amortized O(1) (constant time on average), giving amortized O(n) overall.

Recognizing it in an interview

The hard part is not the code — it is spotting that a problem wants a monotonic stack. Train your ear for these recognition signals; when a prompt asks, for each element, about the nearest element that is bigger or smaller in some direction, a monotonic stack is almost always the intended O(n) answer:

• "For each element, find the next greater / next smaller element to the right (or left)." — the textbook case.
• "Daily Temperatures: for each day, how many days until a warmer temperature?" — next-greater in disguise; the answer is the distance to the popper.
• "Largest rectangle in a histogram" / "maximal rectangle" — uses a stack to find, for each bar, the nearest shorter bar on each side.
• "Stock span," "next greater element with wraparound," "remove k digits to make the smallest number" — all maintain a monotonic invariant.
• Any time the brute force is "for each i, scan in one direction until a condition flips," and you need to collapse that O(n²) scan into O(n).

Pitfalls

• Increasing vs. decreasing. "Next greater" needs a decreasing stack (pop when the newcomer is bigger); "next smaller" needs an increasing stack (pop when the newcomer is smaller). Picking the wrong direction is the most common mistake — re-derive it from what each pop should mean.
• Strict vs. non-strict (> vs >=). Whether you pop on ties decides how duplicates are handled. For "strictly greater" use >; if equal values should also be resolved, use >=. Get this wrong and duplicate-heavy inputs break.
• Store indices, not values, when you need positions, distances, or to write back into an answer array (as in Daily Temperatures). Look up the value with nums[stack_top] only when comparing.
• Leftovers on the stack. Elements still on the stack at the end never found their answer — make sure your default (often -1 or 0) is correct for them.
• Empty-stack guard. Always check the stack is non-empty before peeking the top, or the pop loop will crash on the first element.

Maintain a stack that's always strictly increasing (or decreasing). Each push potentially pops smaller predecessors; each pop resolves an unanswered "next greater" / "left boundary" query.

def trap(h):
    l, r = 0, len(h) - 1
    lmax = rmax = total = 0
    while l < r:
        if h[l] < h[r]:
            lmax = max(lmax, h[l]); total += lmax - h[l]; l += 1
        else:
            rmax = max(rmax, h[r]); total += rmax - h[r]; r -= 1
    return total

function trap(h: number[]): number {
  let l=0, r=h.length-1, lmax=0, rmax=0, total=0;
  while (l < r) {
    if (h[l]<h[r]) { lmax=Math.max(lmax,h[l]); total+=lmax-h[l]; l++; }
    else           { rmax=Math.max(rmax,h[r]); total+=rmax-h[r]; r--; }
  }
  return total;
}

For contrast, here is the monotonic-stack shape itself (next-greater / Daily Temperatures), so you can see the invariant in real code. The stack holds indices; we pop while the current bar is taller than the bar at the top index, and the distance to the popper is the answer.

def daily_temperatures(t):
    ans = [0] * len(t)
    stack = []                       # holds indices; values strictly decreasing
    for i, temp in enumerate(t):
        while stack and t[stack[-1]] < temp:   # newcomer resolves the top
            j = stack.pop()
            ans[j] = i - j           # distance to the warmer day
        stack.append(i)              # keep the invariant, then push
    return ans                        # leftovers stay 0: no warmer day ever came

Next greater element for each index — monotonic stack: