Next Greater Element with a Monotonic Stack
For each element, find the first larger value to its right. The nested-loop version is obvious and quadratic; the stack version is linear and looks like sleight of hand until you notice what it is really doing — throwing away elements that can never be the answer to anything again.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
vector<int> nextGreater(vector<int>& a) {
int n = a.size();
vector<int> res(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.back()] < a[i]) {
res[st.back()] = a[i];
st.pop_back();
}
st.push_back(i);
}
return res;
}
int main() {
vector<int> a = {4, 5, 2, 25, 7, 8};
vector<int> r = nextGreater(a);
for (int x : r) cout << x << ' ';
return 0;
}Stores indices, not values, so the answer can be written back to the correct position; unresolved elements keep their -1.
How it works, step by step
The stack holds unanswered questions
Every index on the stack is an element still waiting for a larger value to appear. Once a[i] resolves it, the index leaves and never returns. The stack size is the number of open questions, not a window.
It stays decreasing, and that is the invariant
Values referenced by the stack are strictly decreasing from bottom to top. When a[i] arrives, it pops everything smaller — and because the stack was decreasing, everything it can resolve sits contiguously on top. That is why one while loop suffices.
A popped element is answered forever
a[i] is the first value to its right that exceeded it, by construction: any earlier candidate would have popped it sooner. So res is written exactly once per index and never revised.
Why it is O(n), not O(n squared)
Each index is pushed once and popped at most once, so the total number of while-loop iterations across the whole run is bounded by n. The inner loop can be long on one step and empty on the next, but the sum is linear.
Leftovers are genuine -1s
Anything still on the stack at the end never found a larger element to its right, so the pre-filled -1 is the correct answer. No cleanup pass is needed — the initialisation already handles it.
Complexity
Amortised linear because every index enters and leaves the stack at most once; the space is worst-case n, hit by a strictly decreasing array where nothing is ever resolved until the end.
Common bugs
Pushing values instead of indices
If the stack holds a[i] rather than i, you know which value was resolved but not where to write the answer. Duplicate values make it unrecoverable. Store indices and dereference with a[st.back()] when you need the value.
Using <= instead of < in the pop condition
a[st.back()] <= a[i] pops equal elements, which answers next greater or equal rather than strictly greater. On {2, 2, 3} it reports 2 for the first element instead of 3. Which one is correct depends on the problem statement, and mixing them up is a silent off-by-one in semantics.
Checking a[st.back()] before checking empty()
Reversing the operands in the while condition calls back() on an empty vector, which is undefined behaviour rather than a crash. It usually reads garbage that happens to be large, so the loop exits and the code appears to work — until it does not.
Assuming the stack is a sliding window
The stack is not the recent k elements; it is a decreasing subsequence that can span the entire array. On strictly decreasing input it holds every index at once. If you sized a fixed buffer for it, watch it grow past your assumed bound on {9,8,7,6,...}.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is a monotonic stack?
A stack whose contents are kept in sorted order — increasing or decreasing — by popping elements that would violate that order before each push. The pops are not overhead: each popped element is being resolved at exactly the right moment, which is what makes these algorithms linear.
Why is next greater element O(n) with a stack?
Because each index is pushed exactly once and popped at most once across the entire run, so the total work in the inner while loop is bounded by n regardless of how it is distributed. The brute force is O(n squared) because it re-scans the same elements for every starting position.
Why does the stack store indices instead of values?
Because when an element is finally resolved you have to record the answer at its original position. A value alone does not tell you where it came from, and duplicate values make it impossible to guess. Keeping indices lets you read the value with a[st.back()] whenever you need it.
What other problems use a monotonic stack?
Largest rectangle in a histogram, trapping rain water, daily temperatures, and stock span — all of them ask for the nearest element on one side satisfying a comparison. If you can phrase the question as nearest smaller or larger to the left or right, a monotonic stack solves it in one pass.