Monotonic Stack

Find the next or previous greater or smaller element for every position in one O(n) pass, with a stack that stays sorted from bottom to top.

Overview

The idea

Many problems ask, for every element of an array, where the nearest larger (or smaller) element is. Checking each element against everything to its right costs O(n²). A monotonic stack answers every position in one pass.

The stack holds indexes whose values are sorted from bottom to top. Each index on it is still waiting for its answer. When a new element arrives, it is compared with the top. Every top it beats is popped, and the new element is that popped index's answer. Then the new index is pushed. Because an index is pushed once and popped at most once, the whole pass is O(n).

For each element, scan to the right until a larger one appears — up to about 5 billion (n² ÷ 2) — O(n²)
Monotonic stack — at most about 200,000 (one push and one pop per index) — O(n)

The numbers come from n(n − 1) ÷ 2 = 4,999,950,000 and 2n = 200,000.

One step

For the next greater element, the stack keeps values decreasing from bottom to top. A new element pops every top that is smaller than it.

After the loop, every index still on the stack has no greater element to its right. Give those the default the problem asks for, usually −1.

A trace

Next greater element on [4, 2, 7, 5, 3, 6]. The stack shows values, but the code stores indexes.

0 — 4 — none — 4 — −1, −1, −1, −1, −1, −1
1 — 2 — none — 4, 2 — −1, −1, −1, −1, −1, −1
2 — 7 — 2, then 4 — 7 — 7, 7, −1, −1, −1, −1
3 — 5 — none — 7, 5 — 7, 7, −1, −1, −1, −1
4 — 3 — none — 7, 5, 3 — 7, 7, −1, −1, −1, −1
5 — 6 — 3, then 5 — 7, 6 — 7, 7, −1, 6, 6, −1

The 7 and the 6 stay on the stack, so their answers remain −1.

Which direction

The pop condition decides what the stack finds. Read the table before you write the loop, and say your choice out loud.

Next greater to the right — nums[top] nums[i] — increasing — nums[i]
Previous greater to the left — nums[top] = nums[i] — increasing — the top left after popping, for index i itself

One pass gives both neighbors: the popped index learns its right neighbor, and the new index reads its left neighbor from whatever remains on top. With a single pop condition one side is strict and the other is not: popping on = rather than > is safe here. Equal bars are popped early with a too-narrow width, but the last bar of the run gets the full width, so the maximum is still found.

Wrap-around

Next Greater Element II treats the array as a circle: the answer for the last element may be near the start. Run the loop for 2n steps with i % n, but push only during the first n steps. The second pass only resolves indexes that are still waiting. The trace below runs on [1, 2, 1].

0 — 0 — 1 — 1 — −1, −1, −1
1 — 1 — 2 — 2 — 2, −1, −1
2 — 2 — 1 — 2, 1 — 2, −1, −1
3 — 0 — 1 — 2, 1 — 2, −1, −1
4 — 1 — 2 — 2 — 2, −1, 2
5 — 2 — 1 — 2 — 2, −1, 2

The 2 is the largest value, so it keeps −1.

Counting with both neighbors

Some problems want, for each element, how many subarrays it is the minimum of. That count is (i − previous smaller) × (next smaller − i): the choices for the left end times the choices for the right end. Sum of Subarray Minimums adds value × count over all elements.

[3, 1, 2, 4], using strict on the left and non-strict on the right:

3 — −1 — 1 — 1 × 1 = 1 — 3
1 — −1 — 4 (none) — 2 × 3 = 6 — 6
2 — 1 — 4 (none) — 1 × 2 = 2 — 4
4 — 2 — 4 (none) — 1 × 1 = 1 — 4

The sum is 17, which matches adding the minimum of all ten subarrays by hand.

What you will be able to do

Pick the pop condition for next or previous, greater or smaller, and handle equal values on purpose.
Explain why the nested while loop is still O(n).
Use indexes on the stack to get spans and widths, not only values.
Solve histogram-style problems by scoring a bar at the moment it is popped.
Handle circular arrays with a 2n loop and count subarrays with the two-neighbor product.

When to use it

For each element, the nearest greater or smaller element to its left or right
Spans and distances: how many days until a warmer one, how many earlier prices were at or below today
Rectangles and areas bounded by the nearest shorter bar on each side (histogram, maximal rectangle)
How many people or buildings an element can see before a taller one blocks the view
Counting subarrays where an element is the minimum or maximum (previous and next smaller in one pass)
Circular versions of the above, with a loop of 2n steps

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio