Monotonic Stack Technique Explained

A monotonic stack is a stack that’s kept either strictly increasing or strictly decreasing from bottom to top, by popping off any element that would break the order before pushing a new one. That single discipline — pop while the invariant would break, then push — turns a family of problems that look like they need nested loops into ones that run in linear time.

It shows up constantly in interview problems (next greater element, largest rectangle in a histogram, daily temperatures) but it’s not just a puzzle trick. The same idea underlies real systems: sliding-window maximum queries, stock span calculations, and compilers tracking matching brackets all lean on a stack that maintains order as it goes.

The core idea

Say you want, for every element in an array, the index of the next element to its right that’s strictly greater. The brute-force approach checks every pair — O(n²). A monotonic stack does it in O(n) by processing each element once and using the stack to remember “elements still waiting for their next-greater value.”

Walk through it left to right. For each new element:

1. While the stack is non-empty and the top of the stack is smaller than the current element, pop it — the current element is that top’s next-greater value. Record the answer.
2. Push the current element (or its index) onto the stack.

Elements that never get popped simply have no next-greater element (their answer is typically -1 or null). Each element is pushed once and popped at most once, so the total work across the whole array is O(n), not O(n²).

arr = [2, 1, 5, 6, 2, 3]

i=0 (2): stack=[]        -> push -> stack=[2]
i=1 (1): stack=[2]       -> 1 < 2, push -> stack=[2,1]
i=2 (5): pop 1 (5>1, ans[1]=5); pop 2 (5>2, ans[0]=5) -> push -> stack=[5]
i=3 (6): pop 5 (6>5, ans[2]=6) -> push -> stack=[6]
i=4 (2): 2 < 6, push -> stack=[6,2]
i=5 (3): pop 2 (3>2, ans[4]=3) -> push -> stack=[6,3]

result: [5, 5, 6, -1, 3, -1]

Notice the stack itself stays monotonically decreasing at every step ([6, 3] at the end) — that invariant is what makes the pop condition correct and what gives the pattern its name.

Increasing vs decreasing stacks

Which direction you maintain depends on what you’re looking for:

• Decreasing stack (pop while top < current): finds the next greater element for each item.
• Increasing stack (pop while top > current): finds the next smaller element for each item.

Reading the array right to left instead of left to right flips “next” into “previous,” so the same two variants also give you previous greater and previous smaller elements. Four small variations, one underlying mechanism.

Where it actually gets used

Largest rectangle in a histogram. For each bar, you need the nearest shorter bar to its left and right to know how far a rectangle at that height can stretch. That’s exactly “previous smaller” and “next smaller,” computed with two passes of an increasing stack.

Daily temperatures. Given a list of daily temperatures, find how many days until a warmer day. This is next-greater-element with a twist: you return the distance between indices rather than the value.

Stock span problem. For each day’s stock price, find how many consecutive prior days had a price less than or equal to today’s. A decreasing stack of (price, span) pairs solves it in one pass — a classic complement to windowed approaches like the sliding window technique.

Sliding window maximum. A monotonic deque — a double-ended stack, effectively — maintains a decreasing sequence of candidates for the maximum as a window slides across an array, evicting elements from both ends. It’s a close cousin of the plain monotonic stack and often taught alongside the two-pointers technique.

Bracket and expression matching. Compilers and parsers use a stack to track open delimiters; a monotonic stack is what you get when you additionally care about ordering (e.g. validating that operator precedence increases toward the top).

Why not just use nested loops or a heap

A naive nested loop recomputes “what’s the next greater element” for every position independently, redoing work a stack lets you skip. A heap can answer “what’s the maximum so far” but doesn’t naturally give you positional answers like “next greater element to the right” without extra bookkeeping — the monotonic stack’s ordering property is what makes those positional questions cheap.

It’s also worth contrasting with backtracking algorithms: backtracking explores and prunes a search space, while a monotonic stack never revisits a decision — every element is pushed and popped at most once, which is exactly what keeps it linear. Understanding why that bound holds is itself a good exercise in amortized analysis: each pop looks like it could cost O(n), but summed across the whole run, total pops can never exceed total pushes.

Recognizing when to reach for one

A few signals suggest a monotonic stack fits the problem:

• The question asks for “next greater,” “next smaller,” “previous greater,” or “previous smaller” element, by value or by distance.
• You’re computing, for each element, some property that depends on the nearest element satisfying an ordering condition (histogram widths, trapped rainwater, stock spans).
• A brute-force solution is O(n²) because it recomputes a comparison for every pair, but the comparisons form a pattern where most pairs get resolved as soon as a “breaking” element appears.

If none of that applies — say you need the k largest elements overall rather than a per-position answer — a heap or a sort is usually the better tool, and understanding Big O notation is what lets you tell the two situations apart before you start coding.

The takeaway

A monotonic stack maintains a strictly increasing or decreasing order by popping elements that would violate it before pushing a new one. That discipline turns per-element “find the nearest element satisfying a condition” queries — next greater, next smaller, histogram widths, stock spans — from O(n²) brute force into O(n) linear time, because each element is pushed and popped at most once over the whole run. Once you recognize the “nearest element with a property” shape, reaching for a monotonic stack becomes automatic.