Monotonic Stack Explained: The Next Greater Element Template

A monotonic stack is an ordinary stack with one rule attached: its contents are kept sorted, and anything that would break the order is popped first. That single constraint turns "find the nearest larger element to the right of every position" from an O(n²) scan into one linear pass, and it is the technique behind a whole family of interview problems about spans, widths and next-greater queries.

This covers what the invariant actually buys you, how to pick the direction, the template, and six worked problems in Python.

The pops are the algorithm#

Start with the brute force: for each index, scan right until you find something bigger. That is quadratic, and the reason it is wasteful is that the scans repeat each other — a long descending run gets re-scanned from every one of its positions.

Now keep a stack of indices whose values are decreasing. When a new value arrives, it pops everything smaller than itself. Look at what a pop means: the popped index had nothing bigger between itself and here, and the arriving value is bigger. So the arriving value is that index's next greater element — no search required, just the pop.

That is the whole idea. Every pop resolves exactly one answer, and each index can be popped only once because it is pushed only once. The while loop looks quadratic and is not: at most 2n stack operations happen across the entire run.

Increasing or decreasing: choosing the monotonic stack direction#

Four questions, two stacks. Pick by working backwards from what you want:

The two families are read differently, and this is the part that trips people. For a next query, the answer is assigned to what you pop — the current element is the answer for everything it evicts. For a previous query, the answer is whatever remains on top after the popping, because that is the nearest surviving element to the left.

The next greater element template#

Next Greater Element I is the pattern in its plainest form: for every value in one array, find its next greater element in another.

def next_greater_element(nums1, nums2):
    next_greater = {}
    stack = []

    for value in nums2:
        while stack and stack[-1] < value:
            next_greater[stack.pop()] = value
        stack.append(value)

    return [next_greater.get(value, -1) for value in nums1]

Anything still on the stack at the end never found a larger element, which is why the lookup defaults to -1. O(n + m) time, O(n) space.

Flipping to a previous-smaller query changes two lines — the comparison, and where the answer is read from:

def previous_smaller(nums):
    result = [-1] * len(nums)
    stack = []

    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] >= value:
            stack.pop()
        result[i] = stack[-1] if stack else -1
        stack.append(i)

    return result

This version stores indices, which is what you want in practice: Daily Temperatures is the same loop where the answer is i - popped_index rather than the value, and Next Greater Element II is the same loop run over 2n iterations with i % n, pushing only during the first pass so the array behaves as a circle.

Worked problems#

Online Stock Span#

Problem 901. How many consecutive days back from today had a price at most today's? The elegant part is that a popped entry hands over its own span before it disappears, so history collapses rather than being rescanned.

class StockSpanner:
    def __init__(self):
        self.stack = []

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

Amortised O(1) per call — every price is pushed once and popped once across the object's lifetime.

Largest Rectangle in Histogram#

Problem 84, the problem this pattern exists for. Every bar defines a rectangle whose height is that bar and whose width runs until the first shorter bar on each side. Those are exactly the previous-smaller and next-smaller queries.

def largest_rectangle_area(heights):
    stack = []
    best = 0

    for i, height in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > height:
            top = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        stack.append(i)

    return best

Two details do a lot of work. The appended sentinel 0 forces every remaining bar to be resolved instead of needing a separate drain loop after the scan. And left is the index below the popped one on the stack, not top - 1 — because everything between them was already popped, which means it was all taller. O(n) time, O(n) space.

Trapping Rain Water#

Problem 42 with a stack fills the water in horizontal layers rather than columns. When a bar is popped, it becomes the floor of a basin whose walls are the new bar and whatever is now on top of the stack.

def trap(height):
    stack = []
    water = 0

    for i, current in enumerate(height):
        while stack and height[stack[-1]] < current:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            depth = min(height[left], current) - height[bottom]
            water += width * depth
        stack.append(i)

    return water

The break matters: with nothing left on the stack there is no left wall, so that basin holds nothing and there is no further popping to do. O(n) time and space. The two-pointer solution to the same problem uses O(1) space and is the better answer if the interviewer pushes — worth knowing both and saying so.

Remove K Digits#

Problem 402 is the other half of the pattern, and the half people miss: a monotonic stack is also how you build the smallest or largest sequence under a length budget.

def remove_k_digits(num, k):
    stack = []

    for digit in num:
        while k and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)

    if k:
        stack = stack[:-k]

    return "".join(stack).lstrip("0") or "0"

Greedy plus monotonic: a digit larger than its successor should go, because removing it lowers a more significant place. Two loose ends that cost submissions — leftover budget when the input is already non-decreasing, and leading zeroes, with the empty result mapping to "0". O(n) time.

Sum of Subarray Minimums — counting contributions#

Problem 907 is the pattern's third use, and the one that generalises furthest. It asks for the sum, over every subarray, of that subarray's minimum. Enumerating subarrays is quadratic, so invert the question: instead of asking "what is the minimum of this subarray", ask "how many subarrays is this element the minimum of".

The answer is a product of two distances — how far left you can extend before hitting a smaller element, and how far right — and both are exactly the previous-smaller and next-smaller queries from the table above. One pass with an increasing stack gives every element's contribution, and the total is the sum of value × left_span × right_span.

The trap is duplicates. If both sides use a strict comparison, a subarray whose minimum appears twice gets counted twice; make one side strict and the other non-strict and each subarray is attributed to exactly one occurrence. That asymmetry looks arbitrary until you have been bitten by it once.

Sliding Window Maximum — the deque#

Problem 239 is where the stack becomes a queue. A sliding window can track a sum in constant time because a departing element can be subtracted; it cannot track a maximum the same way, because the departing element might be the maximum.

from collections import deque

def max_sliding_window(nums, k):
    window = deque()
    result = []

    for i, value in enumerate(nums):
        while window and nums[window[-1]] <= value:
            window.pop()
        window.append(i)

        if window[0] <= i - k:
            window.popleft()
        if i >= k - 1:
            result.append(nums[window[0]])

    return result

The deque holds indices in decreasing order of value. The back is where the monotonic invariant is maintained; the front is where indices that have fallen out of the window are discarded. The front is therefore always the current maximum. O(n) time, O(k) space.

How to recognise it#

Three signals, any one of which is enough to make the stack your first guess:

1. The question names a direction and a comparison. "Next warmer day", "previous smaller element", "first taller building to the right".
2. The answer is a span, a width, or a distance between a position and the first position that beats it.
3. The brute force scans outward from every index until it finds something bigger or smaller.

Histograms, skylines, temperatures, stock spans and rainwater are all the same problem wearing different clothes.

Two things to say out loud when you use one. First, the invariant — "I am keeping the stack decreasing, so an arriving larger value resolves everything it pops." Second, the complexity argument, because an interviewer watching a nested loop will ask: each index is pushed once and popped once, so it is O(n) despite the inner while.

More problems on this technique are collected on the monotonic stack pattern hub, and it sits next to the plain stack pattern in the full pattern map. Worth knowing: the Blind 75 contains no monotonic stack problem at all, so if that is your study list you have to add these deliberately.

If you want support during the interview rather than before it, Stealth Interview is a desktop app for macOS and Windows that reads the problem from a screenshot and walks through the approach, the code and the complexity with you, while staying invisible to screen sharing.