Pattern 9 of 27

Monotonic Stack

Keep a stack in increasing or decreasing order so every element finds its next greater or smaller neighbour in one pass.

Cost: O(n) time, O(n) space
Problems: 6

When to reach for it

The prompt asks for the next or previous greater or smaller element.
You need to know how far each element extends before something blocks it.
The brute force scans right from every element with a nested loop.

How it works

Walk left to right and keep a stack of indices still waiting for an answer, in decreasing order of value. When a larger value arrives, it is the answer for every smaller value on top of the stack, so pop them and record it. Each index is pushed once and popped once, which makes the whole scan linear. Histogram areas use the same pops: the moment a bar is popped, you know exactly how far it could stretch on both sides.

The template

Written for Daily Temperatures (write-up)

def daily_temperatures(temps):
    answer = [0] * len(temps)
    stack = []                        # indices, temperatures decreasing
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j         # i is j's next warmer day
        stack.append(i)
    return answer

Open in the editor Trace it line by line

Six problems, in learning order

1.Daily TemperaturesLeetCode 739Pop colder days whenever a warmer day arrives.Medium
2.Next Greater Element ILeetCode 496Precompute the next greater element for nums2 in a map, then look up nums1.Easy
3.Next Greater Element IILeetCode 503Circular array: loop over the indices twice, modulo n.Medium
4.Largest Rectangle in HistogramLeetCode 84When a bar is popped, its width runs from the new stack top to the current index.Hard
5.Maximal RectangleLeetCode 85Build a histogram for each row, then reuse Largest Rectangle in Histogram.Hard
6.Online Stock SpanLeetCode 901The online version: each price pops smaller earlier prices and absorbs their spans.Not in the curated 370 yet.Medium

What usually goes wrong

Storing values on the stack when the answer needs distances, which requires indices.
Choosing a strict or non-strict comparison wrongly, which double counts equal values.
Forgetting to flush the bars left on the stack when a histogram scan ends.

Monotonic Stack, answered

When should I use the monotonic stack pattern?

The prompt asks for the next or previous greater or smaller element. You need to know how far each element extends before something blocks it. The brute force scans right from every element with a nested loop.

What is the time complexity of monotonic stack?

O(n) time, O(n) space. Histogram areas use the same pops: the moment a bar is popped, you know exactly how far it could stretch on both sides.

Which problem should I start with for monotonic stack?

Start with Daily Temperatures (LeetCode 739, Medium). Pop colder days whenever a warmer day arrives. The six problems on this page are in learning order.