The Invariant That Turns O(n²) Into O(n): Monotonic Stack and Queue

You have an array. You need, for every element, the next element to its right that is larger. The obvious fix is two nested loops: scan forward from each position until you find something bigger. That's O(n²). It also makes your interviewer write something in their notes, and it is not a smiley face.

The monotonic stack does the same thing in a single pass, O(n) total. Not O(n) amortized per element while secretly being O(n²) total. Genuinely O(n) for the whole thing. Here is why.

A monotonic stack is a regular stack with one rule bolted on: its contents stay sorted. You pick a direction, increasing or decreasing, and enforce it on every push by popping anything that would violate the order. The pops are the work. They are not bookkeeping overhead you should feel guilty about. They are the whole point.

Use a monotonic stack when a problem asks about "next" or "previous" neighbors with a relational condition. Its cousin, the monotonic queue (backed by a deque), handles the running extreme of a sliding window in O(n) where a heap would give you O(n log k).

The Invariant: One Rule, Lots of Problems

Pick an array: [3, 1, 4, 2, 5].

A monotonic decreasing stack processes this left to right. When element 4 arrives, the stack holds [3, 1]. Because 4 > 1, we pop 1. Because 4 > 3, we pop 3. Then we push 4. Each element popped has just found its "next greater element": for index 1 (value 1), next greater is 4. For index 0 (value 3), next greater is also 4.

The pop cascade simultaneously enforces the invariant and records relationships. That double duty is the whole trick. Every pop is useful. No element is popped more than once. The whole algorithm is O(n).

How It Works Under the Hood

The Index Store

There is no exotic data structure here. A monotonic stack is a plain array used as an index store. You almost always push indices, not values. The values are compared through the original array.

The stack holds positions, not the numbers at those positions. The invariant lives on the values you look up through those positions.

The invariant is on values looked up through indices, not on the stored integers themselves. Storing indices instead of values is not optional. You need the original position to write results back and to compute distances (like "how many days until a warmer temperature?"). Store values and you will hit this bug in your second interview question on the topic.

The Push Cascade, Step by Step

Here is the full execution for [3, 1, 4, 2, 5] finding next-greater:

Orange highlights mark the pop cascades. Each popped element discovers its answer at the moment it is evicted.

i=0, val=3:  stack=[] → push 0       stack=[0]   (values: [3])
i=1, val=1:  1 < 3, no pops          stack=[0,1] (values: [3,1])
i=2, val=4:  4 > 1 → pop 1, nge[1]=4
             4 > 3 → pop 0, nge[0]=4
             push 2                   stack=[2]   (values: [4])
i=3, val=2:  2 < 4, no pops          stack=[2,3] (values: [4,2])
i=4, val=5:  5 > 2 → pop 3, nge[3]=5
             5 > 4 → pop 2, nge[2]=5
             push 4                   stack=[4]   (values: [5])

Leftover (index 4): no next greater → nge[4] = -1

Elements remaining on the stack at the end never found a qualifying neighbor.

The Deque Variant: Monotonic Queue

A pure stack only lets you remove from one end. When a sliding window slides, you also need to evict the left boundary when it falls out of range. That requires removal from both ends, so you swap the stack for a deque.

The back of the deque behaves like a stack: you push new elements there and pop from there to maintain the invariant. The front holds the window's current extreme. You evict from the front when the index stored there is older than i - k.

Front eviction removes stale indices. Back cascade removes elements that can never be the window max. Both are O(1) amortized.

Window [1, 3, -1]:   dq=[1, 2]   (indices of values 3, -1)  → max = 3
Window [3, -1, -3]:  dq=[1, 2, 3]                           → max = 3
Window [-1, -3, 5]:  push 4 (val=5), both -1 and -3 evicted
                     dq=[4]                                  → max = 5
Window [-3, 5, 3]:   dq=[4, 5]                               → max = 5

The front is always the maximum. The sequence from front to back is always decreasing.

Core Operations

Monotonic Stack

Monotonic Queue (Deque)

Why the Amortized Bound Actually Holds

The inner while loop looks expensive. For one single push, it can pop up to n elements. So O(n) per push, right? O(n²) total?

No. Consider a token argument. Give each element two tokens on entry: one for the push, one for a future pop. The inner while loop consumes the pop token of each element it removes. Because each element can only be inserted once, it can only have its pop token consumed once. Total tokens consumed across all n pushes: at most 2n. That is O(n) total, O(1) amortized per push.

This is the same argument as dynamic array resizing. Doubling the array costs O(n) for that one resize. But each element moves at most once across all appends, so the total copy work across all n appends is O(n).

There is no hidden quadratic cost. The worst case for the entire algorithm, not just one operation, is O(n).

A priority queue cannot replace a monotonic queue for sliding windows. A heap evicts stale elements lazily: you mark them, then ignore them on extraction. That costs O(log k) per operation and O(k) ignored garbage you need to check. The monotonic deque evicts them eagerly from the front in O(1) because stale elements are always at the front.

Implementations

The examples below implement two canonical operations: next_greater (monotonic decreasing stack, next greater element) and sliding_window_max (monotonic decreasing deque, sliding window maximum). Together they cover all the key mechanics of both structures.

from collections import deque

def next_greater(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack: list[int] = []  # indices; values decrease bottom to top
    for i, val in enumerate(nums):
        while stack and nums[stack[-1]] < val:
            result[stack.pop()] = val
        stack.append(i)
    return result

def sliding_window_max(nums: list[int], k: int) -> list[int]:
    result: list[int] = []
    dq: deque[int] = deque()  # indices; values decrease front to back
    for i, val in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= val:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

The Four Variants: Choosing Your Comparison

The comparison operator in the inner while loop is the dial you turn to get different answers. Two axes: traversal direction (left-to-right or right-to-left) and comparison direction (popping smaller or larger).

Pick a quadrant, get a variant. The code barely changes between them.

The incoming element is always the answer for everything it pops. Pick traversal direction and comparison to choose which answer you want.

Strict vs. weak comparison matters for duplicates. Using < pops only strictly smaller elements, leaving equal elements in the stack. Using <= pops equal elements too. For most "next greater" problems you want strict <. For sum-of-subarray-minimums contribution counting, you need asymmetric handling (strict on one side, weak on the other) to avoid double-counting equal elements. This is the kind of thing that looks like a fluke bug in testing until you hit a well-crafted test case with duplicates. It is not a fluke.

What Problems the Monotonic Stack Solves

Next / Previous Greater or Smaller

The direct application. Given [73, 74, 75, 71, 69, 72, 76, 73] (daily temperatures), find the wait until a warmer day. One pass with a decreasing stack. When you pop an index, the current index minus the popped index is the answer. You stored indices. That subtraction works. If you had stored values, you would be sitting there confused.

Sliding Window Extreme

Find the maximum or minimum of every contiguous subarray of length k. A heap gives O(n log k). The monotonic deque gives O(n). The difference matters at scale, and the deque version is also shorter.

Histogram and Span Problems

The largest rectangle in a histogram (LeetCode 84) reduces to: for each bar, find the nearest shorter bar on the left and right. Both are "next smaller element" queries. The monotonic increasing stack hands you both boundaries in a single pass.

The stock span problem asks: how many consecutive days leading up to today had a price less than or equal to today's? Monotonic decreasing stack, one pass, done.

Contribution Counting

Sum of Subarray Minimums (LeetCode 907): for each element, find how many subarrays it is the minimum of. That count equals (i - left_boundary) * (right_boundary - i). Computing both boundaries for every element is two monotonic stack passes, O(n) total. The naive approach is O(n²) or worse. This is also where the strict-vs-weak comparison for duplicates comes back to bite you if you got it wrong.

Recognizing the Pattern

The signals to look for:

• The problem asks about "next" or "previous" neighbors with a relational condition (greater, smaller, at least as large).
• The problem needs a running extreme (max, min) over a fixed-size window.
• A brute-force solution involves looking left or right from each position. That scan is O(n) per element and O(n²) total.
• The problem mentions "spans", "widths", or "areas" that depend on where something becomes smaller or larger.

If you catch yourself writing for j in range(i+1, n) inside a loop over i, stop. Ask whether a monotonic stack can replace the inner loop. It usually can.

Worked Example 1: Daily Temperatures (LeetCode 739)

Problem: given temperatures [73, 74, 75, 71, 69, 72, 76, 73], return an array where each entry is the number of days until a warmer temperature.

Why a monotonic stack fits: each temperature is waiting for a higher temperature to its right. A decreasing stack holds pending temperatures. When a higher value arrives, it resolves every pending entry below it.

def daily_temperatures(temps: list[int]) -> list[int]:
    result = [0] * len(temps)
    stack: list[int] = []  # indices; values are decreasing
    for i, temp in enumerate(temps):
        while stack and temps[stack[-1]] < temp:
            j = stack.pop()
            result[j] = i - j  # days to wait = distance between indices
        stack.append(i)
    return result

One pass, O(n). The distance i - j only makes sense because we stored indices.

Worked Example 2: Sliding Window Maximum (LeetCode 239)

Problem: given nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, return the maximum of each window of size 3.

Why a monotonic deque fits: a heap can tell you the global max but removing a stale element from it costs O(log k). The deque only holds "useful" candidates. Anything smaller than the newest element can never be the window max while the new element is present, so you pop it immediately. Stale left-boundary elements are always at the front, so eviction is O(1).

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result: list[int] = []
    dq: deque[int] = deque()  # indices; values are decreasing front to back
    for i, val in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= val:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Deque space is O(k). Time is O(n). Each element enters and leaves exactly once.

The Non-Obvious Bugs

Storing values instead of indices. This works right up until the problem asks how many positions apart two elements are. Or until you need to write back results by position. Store indices. Always.

Off-by-one on equal elements. Whether you use < or <= in the pop condition changes which element "owns" a given subarray in contribution counting. A solution that looks correct on clean test cases will fail on arrays with duplicates if you get this wrong. It will fail in a specific way that looks random. It is not random.

Using a list with pop(0) instead of a deque in Python. list.pop(0) is O(n) because it shifts every remaining element left. collections.deque.popleft() is O(1). Same problem with array.shift() in JavaScript and array_shift() in PHP. Fine for whiteboarding, not for anything running at scale. Your interviewer may or may not care. Your production workload will.

Recap

• A monotonic stack is a plain stack that enforces a sorted invariant by popping on push.
• The pop cascade is the operation, not just bookkeeping. Each popped element records a relationship with the incoming element.
• Each element is pushed once and popped at most once across the full algorithm. Total operations: O(n). Not O(n) per step, O(n) for everything.
• Use a decreasing stack for next/previous greater. Use an increasing stack for next/previous smaller. Reverse traversal flips "next" to "previous".
• A monotonic queue extends the pattern to sliding windows using a deque so you can evict expired left-boundary elements in O(1).
• Store indices, not values. Strict vs. weak comparison controls duplicate handling.
• Classic problems: Daily Temperatures, Largest Rectangle in Histogram, Sliding Window Maximum, Stock Span, Sum of Subarray Minimums.

If you want to practice explaining this under pressure, SpaceComplexity runs voice-based mock interviews where an AI interviewer asks you to walk through exactly this kind of reasoning. Talking through why the O(n) bound holds is harder than writing the code. You will discover that mid-sentence.

For more on the patterns that show up alongside monotonic stacks, see our writeups on the sliding window algorithm and the dynamic programming framework.

Further Reading

• Introduction to Monotonic Stack, GeeksforGeeks
• Stack (abstract data type), Wikipedia
• std::stack, cppreference
• std::deque, cppreference
• Monotonic Queue to Solve Sliding Window Problems, labuladong