The Monotonic Stack Pattern (Next Greater Element & Friends)

The monotonic stack pattern keeps a stack in strictly increasing or strictly decreasing order so that, for every element, you can answer “what is the nearest bigger (or smaller) value to one side?” in O(1). It collapses a whole family of next greater element questions from O(n²) brute force down to a single O(n) pass.

When to recognize this pattern

• The problem asks for the next greater element or next smaller element (or the previous greater/smaller) for every item in an array.
• You see span-style phrasing: daily temperatures (“days until a warmer day”) or the stock span (“consecutive days the price was ≤ today”).
• A bar-chart objective like largest rectangle in a histogram or maximal rectangle, where each bar’s reach is bounded by the nearest shorter bar on each side.
• Your instinct is a nested loop scanning forward or backward for the first qualifying neighbor — that quadratic scan is exactly what the stack removes.

Increasing vs decreasing

The only design decision is which order the stack maintains, and that follows directly from the question.

A handy mnemonic: the popping condition uses the opposite comparison to the question. Looking for a greater neighbor? Pop while the incoming value is greater — whatever you pop just found its answer. The same stack also gives you the previous greater or smaller element for free: whatever remains directly below an element when you push it is its nearest qualifying neighbor on the left. So a single left-to-right sweep can answer both the “next” and “previous” versions of the question.

One more framing that helps under interview pressure: a monotonic stack is really just a lazy way to resolve queries. You defer each element’s answer until the moment a neighbor proves it — the value that finally pops it. Nothing is ever revisited, which is the whole reason the brute-force nested scan disappears. If you can phrase your problem as “for each i, find the first j to the right (or left) where some monotonic condition flips,” you almost certainly have a monotonic-stack problem. For more on how this fits alongside sliding windows and two pointers, see the 15 core LeetCode patterns.

The template

This is the canonical next greater element sweep. Store indices (not values) so you can also recover distances. For each i, every index still on the stack with a smaller value has now found its next greater element.

def next_greater(nums):
    n = len(nums)
    res = [-1] * n          # default: no greater element to the right
    stack = []              # indices, values strictly decreasing
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            j = stack.pop()
            res[j] = nums[i]   # nums[i] is j's next greater element
        stack.append(i)
    return res

Worked examples

Next greater element (circular)

Problem: For each element in a circular array, find the next greater element going clockwise.

Same decreasing stack, but iterate over 2n indices and read with i % n so the wrap-around is handled for free. Only push during the first pass.

def nextGreaterElements(nums):
    n = len(nums)
    res = [-1] * n
    stack = []                       # indices into nums
    for i in range(2 * n):
        cur = nums[i % n]
        while stack and cur > nums[stack[-1]]:
            res[stack.pop()] = cur
        if i < n:
            stack.append(i)
    return res

O(n) time and O(n) space. The circular trick — double the loop, modulo the read — recurs across many array problems.

Daily temperatures

Problem: Given daily temperatures, return how many days you wait for a warmer day.

Identical to the template, except we want the distance, so store indices and record i - j when we pop.

def dailyTemperatures(temps):
    res = [0] * len(temps)
    stack = []                       # indices, temps decreasing
    for i, t in enumerate(temps):
        while stack and t > temps[stack[-1]]:
            j = stack.pop()
            res[j] = i - j           # days until warmer
        stack.append(i)
    return res

O(n) time, O(n) space. This is the cleanest example of why you keep indices rather than values: the answer is a gap, not a number.

Online stock span

Problem: For each day’s price, return how many consecutive prior days (including today) had a price ≤ today’s.

Maintain a decreasing stack of (price, span) pairs. When a new price beats the top, absorb its span into the running count — this collapses runs of smaller prices in one step.

class StockSpanner:
    def __init__(self):
        self.stack = []              # (price, span) pairs, prices decreasing

    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

Amortized O(1) per call, O(n) overall. Storing the accumulated span on the stack is the key idea — you never re-scan absorbed days.

Largest rectangle in a histogram

Problem: Given bar heights, find the area of the largest rectangle that fits under the skyline.

Keep an increasing stack of indices. When a bar is shorter than the top, that top bar can’t extend further right — pop it and compute its rectangle. The width spans from the new left boundary to the current index. A sentinel 0 at the end flushes the stack.

def largestRectangleArea(heights):
    stack = []                       # indices, heights increasing
    best = 0
    for i, h in enumerate(heights + [0]):   # trailing sentinel
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, height * width)
        stack.append(i)
    return best

O(n) time, O(n) space. The popped bar’s height is fixed; its width runs from the previous stacked index (the nearest shorter bar on the left) to the current shorter bar on the right.

Variations & pitfalls

• Strict vs non-strict. Whether you pop on > or ≥ decides how ties are handled. For “next strictly greater” use >; in span problems you often want ≤ so equal prices are absorbed. Get this wrong and off-by-one ties slip through.
• Indices, not values. Pushing raw values works for “what is the next greater value” but loses the distance and the left boundary you need for temperatures and histograms.
• Forgetting the sentinel. In the histogram, anything left on the stack after the loop never gets measured. Append a trailing 0 (or drain the stack afterward) so every bar is computed.
• Pitfall: leaving the default answer wrong. Initialize to -1 (or 0 for distances) so elements with no qualifying neighbor are handled without a special case.

FAQ

What is a monotonic stack?

A monotonic stack is a regular stack that you keep sorted — either strictly increasing or strictly decreasing — as you push elements. Before pushing a new value, you pop every element that would break the order. The element that finally stops the popping (or the value being popped) gives you the answer to a “next greater” or “next smaller” query in O(1).

When should I use a monotonic stack in an interview?

Reach for it when the problem asks for the next greater element, next smaller element, previous greater/smaller element, how many days until a warmer temperature, the stock span, or the largest rectangle in a histogram. The common thread is finding, for each element, the nearest item to one side that is bigger or smaller.

Why is the monotonic stack O(n) and not O(n²)?

Each element is pushed onto the stack exactly once and popped at most once. Across the whole array that is at most n pushes and n pops, so the total work is O(n) even though there is a nested while loop — the inner loop is bounded by the total number of pops, not by n per iteration.

Should the monotonic stack hold values or indices?

Store indices. With indices you can still read the value via the array, and you also recover distances — like how many days until a warmer temperature or the width of a histogram bar — which raw values alone cannot give you.

Increasing or decreasing — how do I choose?

For next greater element, maintain a decreasing stack and pop while the incoming value is greater. For next smaller element, maintain an increasing stack and pop while the incoming value is smaller. A useful rule: the popping condition uses the opposite comparison to the question you are answering.