The monotonic stack pattern — next greater/smaller element, in one pass

"Find the next larger element for every item in this array" looks like it needs a nested loop, comparing every pair — a monotonic stack solves it in a single O(n) pass, by keeping only the candidates that could still possibly matter.

Intermediate

4 min read

The problem the naive approach solves in O(n²)

def next_greater_naive(nums):
    result = [-1] * len(nums)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # scan FORWARD from i, looking for the first bigger value
            if nums[j] > nums[i]:
                result[i] = nums[j]
                break
    return result

"For every element, find the next element to its right that's strictly larger" looks like it needs comparing every element against every later element — genuinely O(n²) in the worst case (a strictly decreasing array, where every inner loop runs to completion without finding anything). A monotonic stack solves the exact same problem in a single O(n) pass, by being deliberate about which past elements are still worth keeping around as candidates.

The core idea: keep only elements that COULD still be someone's answer

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # holds INDICES, kept in decreasing order of their VALUES
 
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:  # the current number is bigger than the stack's top
            result[stack.pop()] = n            # THAT'S the answer for whatever index was on top
        stack.append(i)
 
    return result
 
next_greater([2, 1, 3, 4])  # [3, 3, 4, -1]

A monotonic stack maintains its elements in strictly increasing (or decreasing, depending on the problem) order at all times — here, the stack holds indices whose values are kept in decreasing order from bottom to top. When a new number arrives that's bigger than the stack's top, that top element has just found its "next greater element" — it gets popped and resolved, and this repeats as long as the new number keeps beating the stack's top, since the same new number is a valid answer for every smaller element it just beat.

Why this is genuinely O(n), not just "usually fast"

Each index gets PUSHED onto the stack exactly ONCE, and POPPED at most
ONCE (either during the main loop, or never, if it never finds a next-
greater element). Total pushes: n. Total pops: at most n. Total work
across the ENTIRE run: O(n), even though the inner while loop can run
multiple times on any single outer iteration.

The genuinely subtle part: even though the while loop can execute multiple times within a single iteration of the outer for loop, the total number of pop operations across the entire algorithm's run can never exceed n, since every index is only ever pushed once and can only be popped once. This is a real, standard "amortized" analysis — a single iteration can look expensive in isolation, but the total work summed across every iteration is bounded by a simple count, not by the apparent nested-loop structure.

Daily temperatures: the exact same pattern, different framing

def daily_temperatures(temps):
    result = [0] * len(temps)
    stack = []  # indices, temps kept DECREASING from bottom to top — same shape as next_greater
 
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index  # how many days until it got WARMER
        stack.append(i)
 
    return result
 
daily_temperatures([73, 74, 75, 71, 69, 72, 76])  # [1, 1, 4, 2, 1, 1, 0]

"How many days until a warmer temperature" is structurally identical to "next greater element" — the only real difference is that the answer stored is the distance between indices (i - prev_index) rather than the value itself. Recognizing that two problems phrased completely differently ("next greater value," "days until warmer," "next building taller than this one") are actually the same monotonic-stack shape underneath is the real skill this pattern rewards — the code barely changes between them.

Recognizing when a monotonic stack is the right tool

The signal to watch for: a problem asking about "the next element that's bigger/smaller than this one" for every element in an array, especially when the naive approach would compare every pair. A monotonic stack fits specifically because each element only needs to be compared against currently-relevant candidates (the stack's contents), not the entire rest of the array — elements that get popped are, by construction, no longer relevant to anything processed later.