Stacks & Queues5 min read

Monotonic Stack

A stack that stays sorted — used to find the next bigger or smaller element fast

build: \(O(n)\)query: \(O(1)\)push: \(O(1)\) amortizedpop: \(O(1)\) amortizedspace: \(O(n)\)

A monotonic stack is a regular stack with one extra rule: it always stays in sorted order — either always increasing from bottom to top, or always decreasing.

To keep the order, whenever you push a new element, you first pop everything that would break the order. This is the key trick.

Next Greater Element — the classic problem

Given an array like [2, 1, 5, 3, 6], find for each element the next element to its right that is greater than it.

For 2 → next greater is 5
For 1 → next greater is 5
For 5 → next greater is 6
For 3 → next greater is 6
For 6 → none

A naive approach checks every pair: \(O(n^2)\). A monotonic stack does it in \(O(n)\).

◈ Watch monotonic stack

← → arrow keys to step · click elements to interact

How the algorithm works

Walk through the array left to right. Maintain a decreasing monotonic stack (largest at bottom, smallest at top):

For each element x, pop elements from the stack while the top is smaller than x.
Each popped element has found its next greater element: it's x!
Push x onto the stack.

Because each element is pushed once and popped at most once, the total work is \(O(n)\). Every element is processed exactly twice.

Other patterns

Monotonic stacks solve many problems (the monotonic queue variant handles sliding window max/min):

Next Smaller Element — use an increasing stack
Largest Rectangle in Histogram — maintain heights in increasing order
Trapping Rain Water — two-pass monotonic stack
Daily Temperatures — classic next greater element variant

Note: Each element is pushed and popped at most once — that's why the whole process is \(O(n)\) even though it looks like nested loops.

Complexity

Build (process array)Each element pushed/popped once

Linear\(O(n)\)

Per element (amortized)Amortized over all operations

Instant\(O(1)\)

Naive brute forceCheck every pair

Quadratic\(O(n^2)\)

Space (stack)Stack holds at most n elements

At most n\(O(n)\)

Next Greater Element

def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
    for i, val in enumerate(arr):
        while stack and arr[stack[-1]] < val:
            result[stack.pop()] = val
        stack.append(i)
    return result

print(next_greater([2, 1, 5, 6, 2, 3]))
# [5, 5, 6, -1, 3, -1]

Output

[5, 5, 6, -1, 3, -1]

Largest Rectangle in Histogram

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

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

Output

Challenge

Quick check

For array [3, 1, 4, 1, 5], what is the 'next greater element' for the value 1 at index 1?

Stack

A pile of plates — the last one you put on is the first one you take off

→

Monotonic Queue

A queue that tracks the max or min of a sliding window in constant time

→