What is a monotonic stack?

A stack kept in sorted order by popping anything that would break the order before pushing. Popping is not waste — the element being popped has just found its answer, which is why 'next greater element' and similar problems collapse from O(n²) to O(n).

How do I recognise a monotonic stack problem?

The phrasing 'next greater', 'previous smaller', 'nearest larger to the right', or anything about spans and rectangles. The common shape is: for each element, find the closest element on one side satisfying a comparison.

Should I use a list or a deque for a stack in Python?

A list — `append` and `pop` from the end are both O(1) and lists are faster than deques for stack use. Use `collections.deque` only when you also need to add or remove at the front, which is what makes it right for queues and BFS.

Why is the monotonic stack O(n) when it has a nested loop?

Each element is pushed exactly once and popped at most once, so the inner while loop runs at most n times across the entire execution. Total work is bounded by 2n regardless of how the pops cluster.

Stacks, Queues, and the Monotonic Stack

A stack answers “what was the most recent thing that…”. That covers matching, undoing, and — in its monotonic form — a family of problems that otherwise need a nested loop.

Stack basics

import time, random
from collections import deque

stack = []
stack.append(1); stack.append(2); stack.append(3)
print(f"stack {stack}   peek {stack[-1]}   pop {stack.pop()}   now {stack}")

queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print(f"queue {list(queue)}   popleft {queue.popleft()}   now {list(queue)}")

stack [1, 2, 3]   peek 3   pop 3   now [1, 2]
queue [1, 2, 3]   popleft 1   now [2, 3]

Use a list for a stack — append/pop at the end are O(1) and faster than a deque. Use a deque for a queue, because list.pop(0) is O(n):

def queue_list(n):
    q = list(range(n))
    while q: q.pop(0)

def queue_deque(n):
    q = deque(range(n))
    while q: q.popleft()

for n in (40_000, 80_000):
    t0 = time.perf_counter(); queue_list(n);  t1 = time.perf_counter()
    queue_deque(n);                            t2 = time.perf_counter()
    print(f"n={n:>6,}  list.pop(0) {t1-t0:7.4f}s   deque.popleft {t2-t1:7.4f}s")

n=40,000  list.pop(0)  0.5102s   deque.popleft  0.0024s
n=80,000  list.pop(0)  2.0418s   deque.popleft  0.0048s

Matching: the classic

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False                      # wrong type, or nothing to close
    return not stack                              # anything left open → unbalanced

for case in ["()", "()[]{}", "(]", "([)]", "{[]}", "", "(", ")"]:
    print(f"  {case!r:<10} → {is_balanced(case)}")

  '()'       → True
  '()[]{}'   → True
  '(]'       → False
  '([)]'     → False
  '{[]}'     → True
  ''         → True
  '('        → False
  ')'        → False

Three failure modes, all handled: wrong closing type, closing with an empty stack, and leftovers at the end. Candidates commonly miss the third — return not stack rather than return True.

The min stack: an O(1) minimum

class MinStack:
    """push/pop/top/get_min all O(1)."""
    def __init__(self):
        self._stack = []
        self._mins = []                           # min of everything at or below each level

    def push(self, x):
        self._stack.append(x)
        self._mins.append(x if not self._mins else min(x, self._mins[-1]))

    def pop(self):
        self._mins.pop()
        return self._stack.pop()

    def top(self):    return self._stack[-1]
    def get_min(self): return self._mins[-1]

ms = MinStack()
for x in [5, 2, 7, 1, 9]:
    ms.push(x)
    print(f"push {x} → top {ms.top()}  min {ms.get_min()}")
print(f"pop {ms.pop()} → min {ms.get_min()}")
print(f"pop {ms.pop()} → min {ms.get_min()}")

push 5 → top 5  min 5
push 2 → top 2  min 2
push 7 → top 7  min 2
push 1 → top 1  min 1
push 9 → top 9  min 1
pop 9 → min 1
pop 1 → min 2

“The insight is that the minimum is a property of a stack state, so it can be stored alongside each level rather than recomputed. Popping restores the previous minimum for free. O(n) extra space; the variant that stores only the values that were minima at the time saves space at the cost of a slightly fiddlier pop.”

The monotonic stack

The pattern that earns this lesson its place.

def next_greater_brute(nums):
    out = [-1] * len(nums)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):        # scan right until something bigger
            if nums[j] > nums[i]:
                out[i] = nums[j]
                break
    return out

def next_greater_stack(nums):
    out = [-1] * len(nums)
    stack = []                                    # indices, values DECREASING
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            out[stack.pop()] = x                  # x is the answer for everything popped
        stack.append(i)
    return out

print(next_greater_stack([2, 1, 2, 4, 3]))

nums = [random.randint(0, 1000) for _ in range(20_000)]
t0 = time.perf_counter(); a = next_greater_brute(nums);  t1 = time.perf_counter()
b = next_greater_stack(nums);                             t2 = time.perf_counter()
print(f"\nbrute O(n²) {t1-t0:7.4f}s   stack O(n) {t2-t1:7.4f}s   same result: {a == b}")

[4, 2, 4, -1, -1]

brute O(n²)  1.8412s   stack O(n)  0.0104s   same result: True

The idea in one sentence, which is what to say out loud:

“I keep a stack of indices whose answers I do not know yet, held in decreasing order of value. When a new element arrives, it is the ‘next greater’ for every smaller element still waiting — so I pop them and record it. Popping is not wasted work; it is an answer being found.”

And the complexity argument, instrumented:

def next_greater_instrumented(nums):
    out, stack = [-1] * len(nums), []
    pushes = pops = 0
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            out[stack.pop()] = x
            pops += 1
        stack.append(i); pushes += 1
    return pushes, pops

p, q = next_greater_instrumented(nums)
print(f"n = {len(nums):,}   pushes {p:,}   pops {q:,}   total {p+q:,} ≈ 2n")

n = 20,000   pushes 20,000   pops 19,982   total 39,982 ≈ 2n

Each element is pushed once and popped at most once. Total work is bounded by 2n no matter how the pops cluster — that is the answer to “but there is a while loop inside a for loop”.

Daily temperatures — same pattern, distance instead of value

def days_until_warmer(temps):
    out = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            out[j] = i - j                        # distance, not value
        stack.append(i)
    return out

print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))

[1, 1, 4, 2, 1, 1, 0, 0]

One line different from next_greater_stack. Recognising these as the same problem is the point of learning the pattern rather than the problems.

Largest rectangle in a histogram

The hardest common monotonic-stack problem, and it is worth being able to derive:

def largest_rectangle(heights):
    """For each bar, the widest rectangle with that bar as the limiting height."""
    stack = []                                    # indices, heights INCREASING
    best = 0
    for i, h in enumerate(heights + [0]):         # sentinel 0 flushes the stack
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            # left boundary: the element now on top, or -1 if the stack is empty
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, height * width)
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))
print(largest_rectangle([]))
print(largest_rectangle([5]))

Two details that are the whole difficulty:

The sentinel + [0] guarantees every remaining bar is popped and measured. Without it, a strictly increasing histogram leaves the stack full and returns the wrong answer.
width = i - left - 1 uses the new stack top as the left boundary, because everything between it and i is at least as tall as the bar being measured. Getting this off by one is the standard bug.

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

print(f"increasing histogram [1,2,3,4,5]")
print(f"  with sentinel    {largest_rectangle([1,2,3,4,5])}")
print(f"  without sentinel {largest_rectangle_no_sentinel([1,2,3,4,5])}  ← wrong")

increasing histogram [1,2,3,4,5]
  with sentinel    9
  without sentinel 0  ← wrong

Nothing was ever popped, so nothing was ever measured.

Sliding window maximum — a monotonic deque

Same idea, both ends:

def sliding_window_max(nums, k):
    dq = deque()                                  # indices, values DECREASING
    out = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()                          # drop indices that fell out of the window
        while dq and nums[dq[-1]] < x:
            dq.pop()                              # x dominates: those can never be the max
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))

nums = [random.randint(0, 10_000) for _ in range(200_000)]
t0 = time.perf_counter(); sliding_window_max(nums, 1000); t1 = time.perf_counter()
naive = [max(nums[i:i+1000]) for i in range(len(nums) - 999)]
t2 = time.perf_counter()
print(f"\nmonotonic deque O(n)   {t1-t0:7.4f}s")
print(f"max() per window O(n·k) {t2-t1:7.4f}s")

[3, 3, 5, 5, 6, 7]

monotonic deque O(n)    0.1204s
max() per window O(n·k)  8.4102s

70×, and it scales with k. The deque needs both ends — expiring from the front and dominating from the back — which is exactly why a plain stack is not enough here.

A queue from two stacks

A classic that tests whether you can reason about amortised cost:

class QueueFromStacks:
    def __init__(self):
        self._in, self._out = [], []

    def push(self, x):
        self._in.append(x)

    def pop(self):
        self._move()
        return self._out.pop()

    def peek(self):
        self._move()
        return self._out[-1]

    def _move(self):
        if not self._out:                         # only when out is empty
            while self._in:
                self._out.append(self._in.pop())

q = QueueFromStacks()
for x in [1, 2, 3]: q.push(x)
print(f"pop {q.pop()}  peek {q.peek()}")
q.push(4)
print(f"pop {q.pop()}  pop {q.pop()}  pop {q.pop()}")

pop 1  peek 2
pop 2  pop 3  pop 4

“Each element moves from the in-stack to the out-stack exactly once in its lifetime, so pop is amortised O(1) even though an individual pop can be O(n). The if not self._out guard is essential — moving on every pop would reverse the order and be O(n) every time.”

Recognising it

SIGNAL                                   REACH FOR
brackets, tags, nested structure         stack, match on pop
"undo", "backtrack one step"             stack
"next/previous greater/smaller"          monotonic stack
"how many days until…"                   monotonic stack (distance)
spans, histograms, rectangles            monotonic stack + sentinel
"maximum in every window of size k"      monotonic deque
evaluate an expression / RPN             stack
implement a queue with stacks            two stacks, amortised

The checklist

print(is_balanced(""), is_balanced("("), is_balanced(")"))
print(next_greater_stack([]), next_greater_stack([1]))
print(largest_rectangle([]), largest_rectangle([5]))
print(sliding_window_max([1], 1))
try:
    MinStack().get_min()
except IndexError:
    print("empty MinStack.get_min() → IndexError (guard it, or document it)")

True False False
[] [-1]
0 5
[1]
empty MinStack.get_min() → IndexError (guard it, or document it)

Empty input, single element, and popping an empty stack are the three that break these solutions. stack[-1] on an empty list raises IndexError, so every peek needs a guard — say whether you are raising or returning None.

Practice

1. Count pushes and pops in a monotonic stack.

n = 20,000   pushes 20,000   pops 19,982   total ≈ 2n

Each element pushed once, popped at most once. This is the answer to “but there’s a while inside a for” — measured rather than argued.

2. Remove the sentinel from the histogram solution.

[1,2,3,4,5]  with sentinel 9   without 0

An increasing histogram never triggers a pop, so nothing is measured. The sentinel is not tidiness — it is correctness.

3. Time the sliding window maximum against max() per window.

deque 0.1204s   max() per window 8.4102s

70×, and the gap grows with k. The deque needs both ends, which is why a stack cannot do it.

4. Move both stacks on every pop in the queue implementation.

order reverses, and every pop becomes O(n)

The if not self._out guard is what makes it amortised O(1). Removing it is the plant in this question.

Next: linked lists and trees — pointers, recursion, and the traversals worth knowing cold.