The Monotonic Stack: How a Θ(n) Trick Beats the Obvious O(n²)

The core idea and the one invariant that matters

A monotonic stack is an ordinary LIFO stack subject to a single discipline: at all times, the values it holds are sorted — either strictly increasing or strictly decreasing from bottom to top. You enforce this not by sorting, but by popping every element that would violate the order before you push the newcomer. For the Next Greater Element (NGE) problem, you keep a stack of indices whose values are decreasing from bottom to top.

The load-bearing observation is this: when you are about to push value a[i] and the top of the stack holds some earlier index j with a[j] < a[i], then a[i] is the next greater element of a[j] — and, crucially, a[j] is now useless for everyone still on the stack below it. Any future element must first pass a[i] (which is larger) before it could ever be compared to a[j]. So j is resolved and discarded forever.

• Invariant (NGE, decreasing stack): for indices on the stack from bottom to top, the array values are strictly decreasing.
• Resolution rule: element i is the answer for every index popped while processing i.
• Direction: scan left→right for "next" queries, right→left for "previous" queries.

Walking the algorithm step by step

Here is the canonical NGE pass. ans[i] ends up holding the value of the next strictly-greater element to the right of i, or -1 if none exists.

function nextGreater(a):
  n = a.length
  ans = array(n, fill = -1)
  stack = []                 // holds indices, a[stack] strictly decreasing
  for i in 0 .. n-1:
    while stack not empty and a[stack.top] < a[i]:
      j = stack.pop()        // a[i] is j's next greater
      ans[j] = a[i]
    stack.push(i)
  return ans                 // indices left on stack have no greater element

Trace it on [2, 1, 3]:

• i=0 (2): stack empty → push. Stack = [0].
• i=1 (1): a[0]=2 ≥ 1, no pop → push. Stack = [0,1], values [2,1] decreasing. ✓
• i=2 (3): a[1]=1 < 3 → pop 1, ans[1]=3. a[0]=2 < 3 → pop 0, ans[0]=3. Push 2. Stack = [2].
• End: index 2 remains → ans[2] = -1. Result: [3, 3, -1].

Two knobs adapt this to every relative: change < to > to get next smaller; keep an increasing stack instead of decreasing; store indices to also recover the distance (as in Daily Temperatures, where you want how many days until it warms up, i.e. i − j).

The complexity derivation — why it is Θ(n), not O(n²)

The inner while loop looks alarming: it can run many times for a single i. The naive worst-case reasoning would multiply the outer n by an inner n and conclude O(n²). That reasoning double-counts. The correct tool is amortized analysis (specifically the aggregate method).

• Every index is pushed exactly once, at its own iteration → n pushes total.
• Every index can be popped at most once; once popped it is gone → at most n pops total.
• Therefore the combined number of stack operations across the entire run is ≤ 2n, independent of input order.

Each push and pop is O(1), so total work is Θ(n). The array on a decreasing input like [5,4,3,2,1] never pops (stack grows to size n and everything is -1); an increasing input like [1,2,3,4,5] pops constantly — but in both cases the sum of inner-loop iterations is bounded by n. This is the textbook example where a single loop iteration is not O(1) yet the aggregate is linear.

• Time: Θ(n) best, average, and worst — there is no bad input.
• Space: O(n) worst case (a fully monotonic input keeps every index on the stack). Best case O(1) auxiliary if the input alternates. The output array is a separate O(n).

The killer application: Largest Rectangle in a Histogram

NGE is the teaching example, but the technique earns its keep on Largest Rectangle in a Histogram (a staple of competitive programming and computational-geometry / image-processing problem sets). Given bar heights h[0..n−1], the maximum-area axis-aligned rectangle is max over i of h[i] × (right[i] − left[i] − 1), where left[i] is the index of the nearest shorter bar to the left and right[i] the nearest shorter bar to the right.

Both boundary arrays are exactly previous-smaller and next-smaller queries — two monotonic-stack passes (or one clever pass). The whole solution is Θ(n) time and O(n) space, replacing a divide-and-conquer O(n log n) or a brute-force O(n²).

function maxRectangle(h):
  h = h ++ [0]            // sentinel forces final flush
  stack = []; best = 0
  for i in 0 .. h.length-1:
    while stack not empty and h[stack.top] >= h[i]:
      height = h[stack.pop()]
      left = stack.empty ? -1 : stack.top
      width = i - left - 1
      best = max(best, height * width)
    stack.push(i)
  return best

This same skeleton, applied row-by-row with a running histogram of consecutive 1s, solves Maximal Rectangle in a binary matrix in Θ(rows × cols).

Where it runs in the real world

The monotonic stack and its two-ended cousin, the monotonic deque, are not just interview candy — they appear anywhere you need order statistics over a sliding or prefix window in linear time:

• Stream analytics & time series: the Stock Span problem (how many consecutive prior days had a price ≤ today's) is a previous-greater query; it underlies technical-analysis indicators and range-of-motion features.
• Sliding-window maximum/minimum: a monotonic deque maintains the window's max in amortized O(1) per step — used in image processing (grayscale morphology / max-filters), audio envelope followers, and DP optimizations like the convex-hull trick and monotone-queue knapsack.
• Compilers & expression evaluation: operator-precedence parsing keeps a stack that is monotonic in precedence, the same discipline as the shunting-yard algorithm.
• Competitive programming libraries: the Cartesian-tree construction and range-minimum preprocessing both use a monotonic stack in Θ(n); it is the standard build step behind an LCA-based O(1) RMQ.

The reference treatment is the amortized-analysis chapter of CLRS (the stack-with-multipop example) and the histogram problem as popularized by ACM-ICPC problem sets.

Pitfalls, edge cases, and variants

The bugs cluster around three decisions — get them explicit and the code writes itself.

• Strict vs. non-strict comparison. Use < vs. <= deliberately: for "next strictly greater" pop on a[top] < a[i]; for "next greater-or-equal" pop on a[top] <= a[i]. Ties in histogram problems are the classic silent off-by-one — using >= lets equal bars merge correctly.
• Store indices, not values. If you keep raw values you lose the ability to compute distances (i − j) and boundaries; almost every real variant wants the index.
• Sentinels. Appending a 0 (histogram) or +∞ guard forces the stack to flush at the end so you don't special-case leftovers.
• Circular arrays. "Next greater in a circular array" is handled by iterating 2n times over i mod n without pushing on the second pass — still Θ(n).
• Direction confusion. "Previous" queries need a right-to-left scan or a mirror of the invariant; running the wrong direction gives a plausible-but-wrong array that passes small tests.

None of these change the asymptotics — the algorithm is Θ(n) throughout — but they are exactly the failure modes reviewers probe.

Next Greater Element: brute force vs. monotonic stack vs. a balanced-BST sweep

Approach	Time	Extra space	Why
Nested loops (brute force)	O(n²)	O(1)	For each i, scan right until a bigger value — quadratic on decreasing input
Monotonic stack	Θ(n)	O(n)	Each index pushed once, popped once → ≤ 2n operations
Sort + balanced BST / segment tree	O(n log n)	O(n)	Order-statistic queries; general but a log factor slower
Sparse table on ranges	O(n log n) build, O(1) query	O(n log n)	Answers arbitrary range max, but overkill for the 'next' variant
Monotonic deque (sliding window max)	Θ(n)	O(k)	Two-ended variant that also evicts from the front by index