Algo VisualizedStart learning

Monotonic Stack

For each day, how long until a warmer one? For each bar, how far can a rectangle stretch? These "next greater" questions look like O(n²) work, yet one stack answers all of them in a single pass.

intermediate⏱ 10 min read

←Builds on

3Stack (LIFO) & Expression EvaluationA monotonic stack is a plain stack that pops everything that can no longer be an answer.0Big-O & Growth RatesEach element is pushed and popped once, so the total is O(n) despite the inner loop.

Leads to→

3Queue (FIFO) & DequeA monotonic deque gives the sliding window maximum: the same idea, popping at both ends.
1Learn2Play3Check4Practice
01

Learn

The idea, the mechanics and the cost.

01The next greater element

Given an array, find for every element the first larger element to its right, or -1 if there is none. For 4 7 3 5 2 6 8 1 the answers are 7 8 5 6 6 8 -1 -1.

The obvious solution scans right from every position until it finds something bigger. On a decreasing array every scan runs to the end, so that is O(n²).

Notice what the slow scan wastes. When we look at 5, the earlier 3 is still waiting for its answer, and 5 is it. Any element is the answer for all the smaller waiting elements just before it. So keep the waiting elements somewhere and let each new value settle as many of them as it can.

For every element: the first larger one to its right47352681−1−1

02A stack that stays decreasing

Keep the indices of the waiting elements on a stack. Scan left to right; for each a[i]:

  • while the stack is not empty and a[top] < a[i]: the answer for top is a[i]; pop it;
  • push i.

Why does popping only from the top suffice? Because the values on the stack are always decreasing from bottom to top. If something below the top were smaller than a[i], the top would be smaller still and already popped. So the moment we meet an element ≥ a[i], everything under it is bigger too and we can stop.

Whatever remains on the stack at the end never met a larger element: its answer is -1. This is the monotonic stack pattern.

752stack (decreasing)6incoming 66 > 2 → answer(2) = 6, pop6 > 5 → answer(5) = 6, pop7 ≥ 6 → stop, push 6i = 5, a = 4 7 3 5 2 6 8 1
At i = 5 the new value 6 answers 2 and 5, then stops at 7.

03Why it is O(n), and its relatives

The inner while loop looks dangerous, but count per element instead of per iteration: every index is pushed exactly once and popped at most once. All the pops in the whole run add up to at most n, so the total work is O(n). This style of counting is called amortized analysis.

Flip the comparisons to get the whole family:

  • next smaller element: pop while a[top] > a[i] (the stack stays increasing);
  • previous greater or smaller: the answer is whatever is on top right before you push i;
  • store distances i − top instead of values for "days until a warmer day".

The largest rectangle in a histogram uses both previous and next smaller elements for every bar.

Every index: pushed once, popped at most once4071325324658617pushpoppushpoppushpoppushpoppushpoppushpoppushpoppushpopat most 2n operations in total → O(n)

Cost at a glance

All next greater answersO(n)
Pushes + pops≤ 2n
Extra memoryO(n)

Remember

  1. Keep the elements still waiting for an answer on a stack; a new element answers every smaller one on top.
  2. The stack stays monotonic (decreasing for next greater), so you can stop popping at the first element that is not smaller.
  3. Each index is pushed once and popped at most once, so the nested loop is still O(n) in total.
02

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the stack on the right: its values always decrease upwards. Each new bar knocks out the smaller ones on top and fills their answers.

Interactive visualizerfocus here, then space ← →
✎ Your input3–10 numbers, 1–99. Try a decreasing array: everything waits until the end.

Array a

4
7
3
5
2
6
8
1
i01234567
a[i]47352681
next greater????????
Stack (indices, values decreasing)
(empty)
currentwaiting in stackanswer found
For each of the 8 values, find the first larger value to its right. Brute force checks every pair, O(n²). A stack of “still waiting” indices does it in one pass.

Pseudocode

 1 stack<int> st;  // indices still waiting for an answer 2 for i in 0..n-1: 3   while !st.empty() && a[st.top()] < a[i]: 4     ans[st.top()] = a[i]; st.pop(); 5   st.push(i); 6 while !st.empty(): ans[st.top()] = -1; st.pop(); 7 // every index pushed once, popped once → O(n)
1 / 1
03

Check

Three questions. Pick an answer to see why.

Q1

Array 2 1 5. When 5 arrives, the stack holds the indices of 2 and 1 (1 on top). What happens?

Q2

On a strictly decreasing array of n elements, how many pops happen during the scan?

Q3

You want the next SMALLER element instead. What changes?

04

Practice

Real problems to lock it in, easiest first.

LeetCodeNext Greater Element I beginner↗LeetCodeDaily Temperatures intermediate↗CSESNearest Smaller Values intermediate↗LeetCodeLargest Rectangle in Histogram advanced↗