What Is a Monotonic Stack? How It Turns O(n²) Into O(n)

The nested loop feels obvious. You have an array. For each element, scan forward to find the next element that's greater. Two loops, O(n²). Done. Submitted. Wrong answer on test case 47.

The monotonic stack solves the same problem in a single pass. Not because it skips work, but because it avoids repeating it. See it once and you'll spot it everywhere.

One Rule, One Weird Trick (No, Really)

A monotonic stack is a regular stack with one extra rule: when you push a new element, first pop everything that violates a monotonic ordering from bottom to top.

That's the whole thing. The elements you pop on the way in have their question answered at that exact moment. You never have to revisit them, which is the part your O(n²) brain refuses to believe until you trace through an example.

If you're fuzzy on how a plain stack works, the stack data structure post covers the mechanics.

What "Monotonic" Actually Means Here

A regular stack holds whatever you throw at it, no questions asked. A monotonic stack adds one rule: the values must stay in monotonically increasing or decreasing order from bottom to top. It enforces this rule by evicting elements that violate it. Loudly. On entry.

Two variants:

Monotonic increasing stack: bottom holds the smallest value, top holds the largest. Before pushing, pop everything larger. Useful for finding the nearest smaller element.

Monotonic decreasing stack: bottom holds the largest value, top holds the smallest. Before pushing, pop everything smaller. Useful for finding the nearest greater element.

Which one you need depends entirely on the question. "Next greater element" calls for a decreasing stack. "Next smaller element" calls for an increasing stack. Once that clicks, picking the right variant is mechanical. You stop agonizing over it by problem three.

Watch It Work: Next Greater Element

Given [2, 1, 5, 6, 2, 3], find the next strictly greater element to the right for each position. Return -1 if none exists.

Expected output: [5, 5, 6, -1, 3, -1]

Walk through it with a monotonic decreasing stack. Store indices, not values, so you can fill in results by position. (Storing values instead is the most common mistake. More on that later.)

i=0, val=2: stack empty, push 0.        stack: [0]
i=1, val=1: 1 < 2, push 1.              stack: [0, 1]
i=2, val=5: 5 > 1 → pop 1, result[1]=5
            5 > 2 → pop 0, result[0]=5
            push 2.                      stack: [2]
i=3, val=6: 6 > 5 → pop 2, result[2]=6
            push 3.                      stack: [3]
i=4, val=2: 2 < 6, push 4.              stack: [3, 4]
i=5, val=3: 3 > 2 → pop 4, result[4]=3
            3 < 6, stop.
            push 5.                      stack: [3, 5]

Remaining (indices 3 and 5) have no next greater: result[3]=-1, result[5]=-1

One pass. Every element answered. No going back.

Step-by-step trace of a monotonic decreasing stack processing the array [2, 1, 5, 6, 2, 3], showing each push and pop with the resulting next-greater-element answers

def next_greater(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack = []  # stores indices

    for i, val in enumerate(nums):
        while stack and nums[stack[-1]] < val:
            index = stack.pop()
            result[index] = val
        stack.append(i)

    return result

function nextGreater(nums: number[]): number[] {
    const result = new Array(nums.length).fill(-1);
    const stack: number[] = [];

    for (let i = 0; i < nums.length; i++) {
        while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
            const index = stack.pop()!;
            result[index] = nums[i];
        }
        stack.push(i);
    }

    return result;
}

Why O(n) and Not O(n²): The Part That Looks Wrong

The while loop nested inside the for loop looks alarming. You have been trained, correctly, to treat nested loops as a red flag. Your gut says O(n²). Your gut is wrong here.

Every element is pushed exactly once and popped at most once, so the total number of stack operations across the entire algorithm is at most 2n. That's the amortized argument. The inner loop does not run n times per outer iteration. Summed across all n iterations, it can only run n times total, because there are only n elements to pop. Once an element is gone, it's gone forever. It doesn't come back to haunt you.

Think of it this way: every element "earns" one pop by being pushed. When the bill comes due, it pays up and leaves. No element ever pops twice.

Space complexity is O(n). In the worst case, a strictly decreasing input ([5, 4, 3, 2, 1]) means every element stacks up before any pops happen. You can't avoid that allocation, but you were already paying O(n) for the result array anyway.

Diagram showing all 6 array elements each getting exactly one push and one pop, with total operations = 2n

For a deeper look at amortized reasoning, this post on amortized time complexity walks through the accounting method.

Decreasing or Increasing? What Gets Revealed on Pop

Pop when the current element breaks the stack's monotonic property. What gets popped has its question answered.

For a monotonic decreasing stack:

Pop when current > stack top
The popped element's next greater element is current

For a monotonic increasing stack:

Pop when current < stack top
The popped element's next smaller element is current

A practical rule: the boundary you're searching for is exactly what triggers the pop. If you're hunting for the nearest greater neighbor, use a decreasing stack so that a larger element triggers pops. If you want the nearest smaller neighbor, use an increasing stack so that a smaller element triggers pops. The thing you want is the thing that causes the eviction.

One subtlety worth testing explicitly: strict vs non-strict inequality in the pop condition determines whether equal elements count as boundaries. Most problems are strict (< not <=), but trace through equal elements before submitting. Equal-element bugs are quiet and embarrassing.

Three Problem Shapes That Use This

Next greater or smaller element. The classic shape. LeetCode 496 (Next Greater Element I) and LeetCode 739 (Daily Temperatures) both live here. Daily Temperatures asks how many days until a warmer day. That's just the distance to the next greater element dressed up in weather metaphors.

Span and range counting. The stock span problem: for each day, how many consecutive previous days had a lower or equal price? The answer is the distance from the current index to the previous greater element's index. One decreasing stack pass, O(n). The same structure appears in problems that count contiguous subarrays satisfying a monotonic bound.

Histogram and boundary problems. The largest rectangle in a histogram (LeetCode 84). For each bar, you want the first shorter bar to its left and the first shorter bar to its right. Two monotonic increasing stack passes (left-to-right and right-to-left) find all boundaries in O(n) total. Trapping Rain Water (LeetCode 42) follows the exact same boundary logic, but with water instead of rectangles. Same structure, more dramatic problem statement.

The monotonic stack problems guide covers the pattern recognition signals that tell you which shape a problem is before you write a single line of code.

The Two Mistakes That Cost People Points

Storing values instead of indices. The stack exists so you can fill results in by position. If you push values, you lose position information and can't update the result array. Push indices. Always. Retrieve the value as nums[index] when you need it. This mistake is so common it's practically a rite of passage.

Getting the pop condition backwards. For a decreasing stack, pop when current > top. For an increasing stack, pop when current < top. Flipping the condition produces wrong answers on any case where the invariant actually fires. Write the condition out explicitly and trace one example by hand before trusting your implementation. Five minutes of tracing saves twenty minutes of debugging a solution that passes the first three examples and then silently explodes.

A third mistake, less common but just as fatal: forgetting to handle the remaining stack elements after the loop finishes. Anything left at the end has no answer in the direction you searched. Set those positions to -1 (or whatever the problem defines as "no answer"). This is the kind of bug that passes all example cases and fails on a sorted input.

Why This Comes Up in Interviews

The monotonic stack earns its place in interview prep for one reason: it converts an obvious O(n²) solution into O(n), and the conversion requires a non-obvious insight.

Interviewers use these problems precisely because the brute force writes itself. Every candidate produces it. The optimal solution requires recognizing that you can answer questions lazily, as you scan forward, rather than eagerly by searching forward from each element. That recognition is what's actually being tested. The code is short. The reasoning is not.

The typical arc: you write the two-loop solution, the interviewer asks if you can do better, and you either recognize the pattern or you don't. That moment is the whole interview. When it goes well, you explain the amortized O(n) argument without prompting, and the interviewer writes down something favorable.

If you want to practice explaining that reasoning out loud under pressure, SpaceComplexity runs voice-based mock interviews with rubric-based feedback on exactly this kind of tradeoff communication. Not just whether your code runs.

To see LeetCode problems using this pattern ranked by difficulty and sorted by which variant they require, the monotonic stack LeetCode problems list covers 13 of them with explanations.