Stack/QueueData structureaka increasing stack, decreasing stack, next greater element stack

Monotonic Stack

A stack whose elements are kept in sorted order by popping everything that would violate the order before each push.

▶ Visualize Pattern: Monotonic Stack Practice (5)

Progress

Definition

A monotonic stack is an ordinary Stack plus one discipline: before pushing x, pop every element that would break monotonicity (for a decreasing stack, pop while top < x). The stack therefore always reads sorted from bottom to top.

The payoff is that each pop is an answer: when x pops y, x is the first element to the right of y that is greater (for a decreasing stack). This turns the O(n²) "next greater element" scan into a single O(n) pass.

The same mechanism yields previous smaller/greater elements, the width of the region an element dominates (largest rectangle in histogram), stock spans, and daily temperatures.

stackO(n)next greater elementamortizedhistogram

Intuition

A mental model before the formal terms.

Picture people of different heights standing in a line, each looking right for the first person taller than themselves. Walk from left to right holding a "waiting list" of people who have not yet seen someone taller. When a new tall person arrives, everyone on the waiting list who is shorter gets their answer at once and leaves the list. Those still waiting are, necessarily, taller than the newcomer, so the list stays sorted tallest-to-shortest.

How it works

Choose the invariant: decreasing (bottom largest) to find next greater, increasing to find next smaller.
Iterate i = 0..n-1. While the stack is non-empty and a[stack.top] violates the invariant relative to a[i], pop j = stack.top and record answer[j] = i (or a[i]).
Push i (store indices, not values, so you can compute distances and widths).
After the loop, indices still on the stack have no next greater element; assign -1 or n.
For "previous greater", read the top of the stack before pushing: it is the nearest surviving element to the left.

Why it works

Elements below x in the stack that were popped by x were smaller than x, and everything between them and x in the array was even smaller (otherwise it would have popped them earlier). So x is genuinely the *first* larger element to their right.

Every index is pushed exactly once and popped at most once, so total work is O(n) regardless of how many pops one push triggers.

Operations

Operation	Description	Cost
push(i)	Pop violating indices (recording answers), then push i.	O(1) amortized
pop()	Remove the top index; the pusher is its next greater/smaller.	O(1)
peek()	The nearest surviving element to the left with the invariant property.	O(1)

Recognition

How to tell a problem wants this.

Phrases: next greater/smaller element, previous greater/smaller, "how many days until a warmer temperature", "stock span".
Largest rectangle / maximal area under a histogram or in a binary matrix.
Sum of subarray minimums/maximums — count how many subarrays each element is the min of.
Any O(n²) nested loop where the inner loop looks for the first element satisfying a comparison to the outer element.

“next greater element” → Monotonic Stack “balanced parentheses” → Stack

Interactive demo

Play, step, change the input. ← → and space work too.

Array — Comma or space separated numbers, up to 40

stack (bottom → top, indices)

next greater

1/24For each element find the next greater element to its right. Indices wait on a stack whose values are strictly decreasing top-to-bottom, so a new bigger value resolves everything smaller in one go.

Current elementWaiting on stackAnswer resolvedNo greater element

PseudocodeLearn Monotonic Stack →

1ans = [-1] * n; stack = []  # indices, values decreasing
2for i in 0 .. n-1:
3  while stack and a[stack.top] < a[i]:
4    ans[stack.pop()] = a[i]
5  stack.push(i)
6return ans

Variables

stackSize0

Complexity

access O(1)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1nextGreater(a):
2  ans = [-1] * n; st = []
3  for i in 0..n-1:
4    while st and a[st.top] < a[i]:
5      ans[st.pop()] = i
6    st.push(i)
7  return ans

Implementation

1class MonotonicStack:
2    """A stack of indices kept strictly decreasing by value. One sweep answers
3    next-strictly-greater and previous-greater-or-equal for every index."""
4 
51 · State: the values, a decreasing stack of indices, and both answers
6    def __init__(self, values: list[int]) -> None:
7        self.values = values
8        self.stack: list[int] = []  # indices; values[stack] is strictly decreasing
9        self.next_greater = [-1] * len(values)
10        self.prev_greater_eq = [-1] * len(values)
11        self.build()
12 
132 · push: pop everything this value dominates; i is their next greater
14    def push(self, i: int) -> None:
15        while self.stack and self.values[self.stack[-1]] < self.values[i]:
16            self.next_greater[self.stack.pop()] = i
173 · Whatever survives the pops is the previous greater-or-equal element
18        self.prev_greater_eq[i] = self.stack[-1] if self.stack else -1
19        self.stack.append(i)
20 
214 · build: one left-to-right sweep; each index is pushed and popped once
22    def build(self) -> None:
23        for i in range(len(self.values)):
24            self.push(i)
255 · Indices still on the stack have nothing greater to their right (-1)

Walkthrough

self.stack[-1] is the peek; the while self.stack and ... guard short-circuits, so the index is never evaluated on an empty list.
self.next_greater[self.stack.pop()] = i mirrors the other languages exactly — list.pop() with no argument removes and returns the last element in O(1).
self.prev_greater_eq[i] = self.stack[-1] if self.stack else -1 is the conditional expression form of the read-the-survivor step; the survivor ties are why this direction is greater-or-equal rather than strictly greater.
[-1] * len(values) allocates and fills in one expression; unlike a list comprehension it does not build an intermediate generator.
Each index is appended once and popped at most once, so the total work of the nested while is linear despite the loop nesting.

Complexity (this implementation)

time O(n) · space O(n)

list.pop() from the end is O(1); list.pop(0) would be O(n) and turn the sweep quadratic.

Language notes

A plain list is the idiomatic Python stack — append/pop are amortised O(1) and collections.deque buys nothing when only one end is used.
[-1] * n is safe for immutable elements; the same idiom with a mutable element ([[]] * n) would alias one list n times.
The while cond and expr short-circuit is what keeps self.stack[-1] from raising IndexError — Python has no undefined behaviour here, it would raise.
Type hints like list[int] need Python 3.9+; on older versions use List[int] from typing.

Common mistakes in this language

Writing while self.values[self.stack[-1]] < self.values[i] and self.stack: — the order matters, this raises IndexError on the empty stack.
Storing values instead of indices, which makes the next-greater *position* unrecoverable.
Using self.stack.pop(0) out of habit, which is O(n) per call and makes the whole sweep O(n²).

Language differences that matter here

Peeking the top: C++ stack.back(), JS/TS stack[stack.length - 1] (or at(-1)), Python stack[-1] — only Python has real negative indexing.
Empty-stack access: C++ back() on an empty vector is undefined behaviour, Python raises IndexError, and JS/TS quietly return undefined — the guard is mandatory in all three but only C++ fails silently and dangerously.
Array preallocation: C++ std::vector<int>(n, -1) and Python [-1] * n fill eagerly; JS/TS new Array(n) creates holes unless you .fill(-1).
The comparison itself is numeric in all four, but JS/TS < on strings is lexicographic and Python < on mixed types raises — C++ needs an explicit comparator for anything but built-in scalars.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Top only.
Search	O(n)	O(n)
Insert	O(1)	O(n)	One push may pop many, but total pops ≤ total pushes.
Delete	O(1)	O(1)
Update	—	—
Push (with pops)	O(1) amortized	O(n)
Pop	O(1)	O(1)
Peek	O(1)	O(1)
Full pass over n elements	O(n)	O(n)
Space	O(n)

Advantages & disadvantages

Advantages

Reduces an entire family of nearest-element problems from O(n²) to O(n).
Trivial to implement on top of any array-backed stack.
Answers both "next" (at pop time) and "previous" (at push time) queries in one pass.

Disadvantages

Only handles nearest-element questions in a single scan direction; not a general range query structure.
Choosing strict vs. non-strict comparison is subtle and changes the answer for duplicates.
Offline only: it cannot answer arbitrary queries after arbitrary updates (use a Segment Tree for that).

Use cases

Next/previous greater or smaller element arrays.
Largest rectangle in a histogram and maximal rectangle in a binary matrix.
Daily temperatures, stock span, online stock span.
Trapping rain water (stack variant) and sum of subarray minimums.

Use it when

You need, for every element, the nearest element to the left or right that is larger or smaller.
You need to know the maximal span in which an element is the minimum/maximum (histogram, subarray-min sums).
The array is processed in one direction and no updates occur.

Avoid it when

Queries are over arbitrary ranges rather than "nearest" — use a Segment Tree or Sparse Table.
The window slides and you need the max/min inside it — that is a Monotonic Queue.
The array changes between queries.

Alternatives

Monotonic Queue Segment Tree Sparse Table

Common mistakes

Storing values instead of indices, losing the ability to compute distances or widths.
Using <= where < is required (or vice versa) — decides whether equal elements pop each other, which matters for counting subarrays with duplicates.
Forgetting to process the leftover stack after the loop (elements with no next greater, or histogram bars extending to the right edge).
Trying to answer "previous greater" from pop events; it is read from the top *before* pushing.

Interview patterns

Daily Temperatures / Next Greater Element I & II (circular: iterate 2n indices with % n).
Largest Rectangle in Histogram: increasing stack; on pop, width = i - stack.top - 1.
Sum of Subarray Minimums: count left * right spans per element with strict/non-strict asymmetry to avoid double counting.
Remove K Digits / Remove Duplicate Letters: greedy stack that pops larger characters while budget remains.

Interview questions on this

Deciding whether O(n²) can be improvedIntermediate
Stack versus queueBeginner
Next greater element and the monotonic stackIntermediate

Mock interviews

Daily TemperaturesIntermediate

Interview problems

Trapping Rain Waterhard Daily Temperaturesmedium Next Greater Elementeasy Largest Rectangle in Histogramhard Car Fleetmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related