Monotonic stack is the most under-taught pattern in interview prep. People learn two-pointers, sliding window, binary search, BFS, DFS, even union-find before they learn this one, and as a result they fall into the same trap I did for two years: they spot the structure, can't articulate it, and write O(n^2) brute-force on problems that have an O(n) answer staring back at them. The pattern is a stack. The discipline is that the stack is always sorted. The technique is that as you scan, you pop everything on the stack that violates the order. That is the whole idea, and it is enough to crack four or five distinct problems that look unrelated on the surface.

The stance of this article is that monotonic stack is a first-tier pattern, not an exotic trick, and you should learn it the same week you learn sliding window. The reason it gets skipped is that it has a less catchy name and the canonical problems do not telegraph the pattern in their statements. "Daily temperatures" sounds like a sliding-window problem. "Largest rectangle in histogram" sounds like a divide-and-conquer problem. They are both monotonic stack, and once you see it, you cannot unsee it.

What "monotonic" means and why a stack

A monotonic stack is a stack where the elements (or their indices) maintain a strict ordering at all times: monotonically increasing from bottom to top, or monotonically decreasing. When you push something that would violate the order, you pop until the order is restored, then push.

The pop step is where the work happens. Each element popped is being compared against the new arrival, and that comparison is exactly the bit of information the problem needs. "What's the next greater element?" is answered the moment the popping element gets popped: the new arrival is its next greater element. "What's the largest rectangle ending at index i?" is answered when the bar shorter than the previous bar arrives: the previous bar's rectangle has just closed. The pattern reuses the stack's last-in-first-out property to make the relevant question always be about the top of the stack, never about a faraway element.

Why does this give O(n) instead of O(n^2)? Because each element is pushed once and popped at most once. The total number of push-pop operations across the whole scan is 2n. The naive nested loop visits the same pair of indices many times; the monotonic stack visits each pair at most once.

The canonical problem: daily temperatures

Given temps = [73, 74, 75, 71, 69, 72, 76, 73], return for each day the number of days you have to wait until a warmer temperature, or 0 if it never gets warmer. The answer is [1, 1, 4, 2, 1, 1, 0, 0].

The naive solution is O(n^2): for each day, scan forward until you find a warmer day. The monotonic-stack solution is O(n):

function dailyTemperatures(temps) {
    const result = new Array(temps.length).fill(0);
    const stack = [];   // stack of indices, temperatures monotonically decreasing
    for (let i = 0; i < temps.length; i++) {
        while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
            const j = stack.pop();
            result[j] = i - j;
        }
        stack.push(i);
    }
    return result;
}

The stack holds indices, and the temperatures at those indices are monotonically decreasing from bottom to top. When a warmer temperature arrives at index i, every index on the stack with a cooler temperature gets popped, and i - j is the answer for that day.

Monotonic-stack walk on [73, 74, 75, 71, 69, 72, 76, 73]

step i=0  push 0       stack: [0]              (temps: [73])
step i=1  74>73 pop 0  result[0]=1
          push 1       stack: [1]              (temps: [74])
step i=2  75>74 pop 1  result[1]=1
          push 2       stack: [2]              (temps: [75])
step i=3  71<75 push 3 stack: [2, 3]           (temps: [75, 71])
step i=4  69<71 push 4 stack: [2, 3, 4]        (temps: [75, 71, 69])
step i=5  72>69 pop 4  result[4]=1
          72>71 pop 3  result[3]=2
          72<75 push 5 stack: [2, 5]           (temps: [75, 72])
step i=6  76>72 pop 5  result[5]=1
          76>75 pop 2  result[2]=4
          push 6       stack: [6]              (temps: [76])
step i=7  73<76 push 7 stack: [6, 7]           (temps: [76, 73])
end       result[6]=0, result[7]=0 (still on stack, no warmer day exists)

The stack invariant (monotonically decreasing temperatures from bottom to top) holds at every step. Every index is pushed once and popped at most once. Eight push operations, six pop operations, total work is O(n).

Note two implementation details that I see beginners get wrong. First, the stack stores indices, not values, because we need both the temperature (to compare) and the position (to compute the gap). Second, the comparison is strict (>, not >=); for problems where ties should also be popped, change it to >=. Get the comparison wrong and the answer is silently off by one in the tie cases.

Variation: largest rectangle in histogram

This is the problem that convinced me the pattern is fundamental. Given heights [2, 1, 5, 6, 2, 3], find the area of the largest rectangle that fits inside the histogram. Answer: 10, formed by heights [5, 6] of width 2.

The insight is that for each bar, the largest rectangle that uses that bar as its shortest height extends leftward to the first shorter bar and rightward to the first shorter bar. "First shorter bar to the left" and "first shorter bar to the right" are exactly the questions monotonic stack answers in O(n).

function largestRectangleArea(heights) {
    const stack = [];   // indices of bars with monotonically increasing heights
    let maxArea = 0;
    for (let i = 0; i <= heights.length; i++) {
        const h = (i === heights.length) ? 0 : heights[i];
        while (stack.length && heights[stack[stack.length - 1]] > h) {
            const top = stack.pop();
            const left = stack.length ? stack[stack.length - 1] : -1;
            const width = i - left - 1;
            maxArea = Math.max(maxArea, heights[top] * width);
        }
        stack.push(i);
    }
    return maxArea;
}

The stack holds indices in increasing height order. When a shorter bar arrives at index i, we pop the top: the rectangle of height heights[top] extends from left + 1 (just after the new top of the stack) to i - 1. Width is i - left - 1.

The sentinel trick of treating i = heights.length as a height-0 bar flushes the remaining stack at the end. Without the sentinel, you would need a second loop to drain the stack, which works but doubles the code. The single-loop sentinel version is cleaner.

Variation: trapping rain water

Given elevations [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], compute how much water is trapped after rain. Answer: 6.

Monotonic stack handles this by, again, finding the boundaries. For each bar that is a local valley, water is trapped up to the minimum of the highest bar to its left and the highest bar to its right.

function trap(heights) {
    const stack = [];   // indices of bars in monotonically decreasing heights
    let total = 0;
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[i] > heights[stack[stack.length - 1]]) {
            const bottom = stack.pop();
            if (!stack.length) break;
            const left = stack[stack.length - 1];
            const width = i - left - 1;
            const boundedHeight = Math.min(heights[i], heights[left]) - heights[bottom];
            total += width * boundedHeight;
        }
        stack.push(i);
    }
    return total;
}

The pattern is identical to the histogram problem. The stack holds indices in decreasing height order. When a taller bar arrives, we pop the bottom of the basin, and the water added is the bounded height times the width of the basin.

This problem also has a two-pointer solution that I find slightly more elegant for this specific case, but the monotonic-stack version generalises better to higher-dimensional variants (trapping rain water 2D, for example).

When the pattern is increasing vs decreasing

The direction of the monotonicity is dictated by what question you are asking:

• Next greater element -> monotonically decreasing stack. You pop when something larger arrives.
• Next smaller element -> monotonically increasing stack. You pop when something smaller arrives.
• Previous greater / smaller element -> same logic but you scan right-to-left, or you read the stack at push time before popping.
• Largest rectangle in histogram -> monotonically increasing, because you want to know the previous shorter bar and the next shorter bar (the boundaries of the rectangle).
• Trapping rain water -> monotonically decreasing, because you want to know the previous taller bar and the next taller bar (the boundaries of the basin).

A quick mnemonic that works for me: write down what you are asking, point at the diagram, and ask "when do I want the stack to give up its element". If the answer is "when something larger arrives", the stack is decreasing. If "when something smaller arrives", increasing.

How to recognise it in the wild

The pattern shows up when the problem statement implies, even indirectly, one of these phrases:

• "For each element, find the next/previous greater/smaller element."
• "For each position, find the maximum/minimum span where it dominates."
• "Find the maximum area / volume / sum that is bounded by some monotonic property."
• "Find the optimal pairing where one element is an ancestor or successor in some sorted-but-with-deletions order."

When I see "for each element" and "some condition involving order" in the same sentence, my hand reaches for the monotonic stack template before I have finished reading the problem. The conditions where it does NOT apply: when the relevant comparison is not pairwise but involves ranges (sliding window maximum is monotonic deque, not stack); when the data is not a flat array (tree problems usually want a different structure); when the cost function is multiplicative or non-monotonic.

I keep this list of LeetCode-style problems pinned in my notes as the practice set: Daily Temperatures, Next Greater Element I and II, Largest Rectangle in Histogram, Maximal Rectangle, Trapping Rain Water, Sum of Subarray Minimums, Online Stock Span, Remove K Digits, 132 Pattern. Solving any five of those means you have the pattern; solving all nine means you can teach it.

The pattern, restated as a claim

Monotonic stack is O(n) answers to questions that look quadratic, and the discipline is one invariant (the stack stays sorted) plus one rule (pop until the invariant is restored before you push). Every problem in the family is a different way of reading the pop event: in next-greater-element it's the answer for the popped index; in histogram it's the closing of a rectangle; in rain water it's the closing of a basin. The shape is the same. The naive brute force on these problems compares every pair of elements; the monotonic stack visits each pair at most once because the stack property guarantees that comparisons against far-away elements are unnecessary. That is the entire trick, and it is too useful to keep relegating to the back of the prep playlist.