Monotonic Stack
A stack kept in sorted (decreasing) order answers "next greater element" and "how far away is it" for every index in one O(n) pass.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
People stand in a line, all looking right. For each person, who is the first taller person they can see?
Walk the line left to right with a stack of people still waiting for a taller person. Keep it decreasing: tallest at the bottom. When a new person arrives, every shorter person at the top of the stack has just found their answer: pop them and record it. Then push the newcomer.
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = a[i]; // next greater
span[st.top()] = i - st.top(); // how far away
st.pop();
}
st.push(i);Each index is pushed once and popped at most once, so the whole thing is O(n).
- Equal values: with
<, an equal height does not count as taller. Use<=if it should. - Circular arrays: loop
ifrom 0 to 2n − 1 and usei % n, pushing only during the first lap. - Store indices, not values, so you can compute distances.
Also see the LeetCode monotonic problems: Car Fleet, Remove K Digits, Sum of Subarray Minimums, 132 Pattern, Shortest Subarray with Sum ≥ K (monotonic queue).
Built on Chapter 5 (stacks). Not on the exam.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Each number pops everything smaller than itself and becomes their answer. Watch the span row fill in.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> nextGreater(const vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1);
stack<int> st; // indices; values decreasing
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) { // a[i] answers everyone smaller
ans[st.top()] = a[i];
st.pop();
}
st.push(i);
}
return ans;
}
vector<int> waitDays(const vector<int>& a) { // span: how far away is the next greater?
vector<int> d(a.size(), 0);
stack<int> st;
for (int i = 0; i < (int)a.size(); i++) {
while (!st.empty() && a[st.top()] < a[i]) { d[st.top()] = i - st.top(); st.pop(); }
st.push(i);
}
return d;
}
vector<int> nextGreaterCircular(const vector<int>& a) {
int n = a.size();
vector<int> ans(n, -1);
stack<int> st;
for (int i = 0; i < 2 * n; i++) { // loop twice to wrap around
while (!st.empty() && a[st.top()] < a[i % n]) { ans[st.top()] = a[i % n]; st.pop(); }
if (i < n) st.push(i);
}
return ans;
}
void print(const char* label, const vector<int>& v) {
cout << label;
for (int x : v) cout << x << " ";
cout << "\n";
}
int main() {
vector<int> a = {2, 1, 3, 5, 6, 1};
print("a: ", a);
print("next greater: ", nextGreater(a));
print("span (j - i): ", waitDays(a));
print("circular greater: ", nextGreaterCircular(a));
}a: 2 1 3 5 6 1 next greater: 3 3 5 6 -1 -1 span (j - i): 2 1 1 1 0 0 circular greater: 3 3 5 6 -1 2
05Complexity
| brute force (scan right from each i) | O(n²) |
|---|---|
| monotonic stack | O(n): each index pushed and popped once |
| Extra space | O(n) |
Pop on < and equal values do not answer each other; pop on <= and they do. For circular arrays, loop twice (i from 0 to 2n − 1, index i % n), pushing only in the first lap.
06Watch
Monotonic Stack Data Structure Explained
Why this one: The data structure itself, explained in under 6 minutes.
Daily Temperatures: Monotonic Stack
Why this one: NeetCode's Daily Temperatures, the span version of this page.
Original class slides (Python, by the course's lecture authors):Stacks, Queues and Monotonicity
07Exam lens
Likely questions
- Why is the monotonic stack O(n) despite the nested while loop?
- How does the answer change if you pop on
<=instead of<? - How do you handle a circular array?
Common mistakes
- Storing values instead of indices, which loses the span (distance).
- Pushing during the second lap of a circular array.
- Forgetting that items left on the stack at the end have no answer (−1).
08Quick check
09Practice
🟢 Trace by hand
Run next-greater on 2 1 3 5 6 1. Write the stack (as values) after each i.
Show answer
- i0:
[2]· i1:[2 1] - i2: 3 pops 1 (ans 3) and 2 (ans 3) →
[3] - i3: pops 3 (ans 5) →
[5]· i4: pops 5 (ans 6) →[6] - i5:
[6 1], leftovers get −1
Answer: 3 3 5 6 -1 -1, spans 2 1 1 1 0 0.
🟡 Implement it
Compute the previous smaller element for every index.
Hint
Scan left to right with an increasing stack. Pop while the top is ≥ a[i]; the top that remains (if any) is the answer.
🔴 Solve problems
Hint
This page's span version.
Hint
Sort by position descending; keep a stack of arrival times; a slower car ahead absorbs the faster ones behind.
Hint
Increasing stack of digits. Pop a bigger digit while k > 0.
Hint
For each i, find how far it is the minimum to the left and right (previous/next smaller). Use
<on one side and<=on the other to avoid double counting.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.