How It Works
As we iterate, we maintain a stack where elements are always in monotonic order. Whenever the new element violates the order, we pop elements (resolving their "next greater/smaller") before pushing the new element.
C++
// MONOTONIC DECREASING STACK — next greater element
// Stack top is always the smallest element seen so far
// When arr[i] > arr[stack.top()]: arr[i] is the NGE for stack.top()
vector<int> nextGreaterElement(vector<int>& arr) {
int n=arr.size();
vector<int> nge(n,-1);
stack<int> st; // stores indices
for(int i=0;i<n;i++) {
while(!st.empty() && arr[i]>arr[st.top()]) {
nge[st.top()] = arr[i]; // found NGE for st.top()
st.pop();
}
st.push(i);
}
return nge;
}
// arr=[2,1,5,4,3] → NGE=[5,5,-1,-1,-1]
// Each element pushed/popped exactly ONCE → O(n)
// MONOTONIC INCREASING STACK — next smaller element
vector<int> nextSmallerElement(vector<int>& arr) {
int n=arr.size();
vector<int> nse(n,-1);
stack<int> st;
for(int i=0;i<n;i++) {
while(!st.empty() && arr[i]<arr[st.top()]) {
nse[st.top()] = arr[i];
st.pop();
}
st.push(i);
}
return nse;
}
Interactive: Next Greater Element
Array [2,1,5,4,3]. Monotonic decreasing stack — when a larger element arrives, pop everything smaller (their NGE is now resolved) before pushing the new element.
Practice Problems
#739Daily TemperaturesMedium
For each day, how many days until a warmer temperature?
Pattern: Monotonic decreasing stack. When warmer day found, pop and record distance.
C++
vector<int> dailyTemperatures(vector<int>& T) {
int n=T.size();
vector<int> res(n,0);
stack<int> st;
for(int i=0;i<n;i++) {
while(!st.empty()&&T[i]>T[st.top()]) {
res[st.top()]=i-st.top();
st.pop();
}
st.push(i);
}
return res;
}
// Time: O(n) Space: O(n)
#496Next Greater Element IEasy
For elements in nums1 (subset of nums2), find next greater element in nums2.
Pattern: Build NGE map for nums2 using monotonic stack. Then lookup each nums1 element in map.
C++
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> nge;
stack<int> st;
for(int n:nums2) {
while(!st.empty()&&n>st.top()) { nge[st.top()]=n; st.pop(); }
st.push(n);
}
vector<int> res;
for(int n:nums1) res.push_back(nge.count(n)?nge[n]:-1);
return res;
}
#84Largest Rectangle in HistogramHard
Find the area of the largest rectangle in a histogram.
Pattern: Monotonic increasing stack. When bar shorter than top found, pop and compute area using popped height and current left/right boundaries.
C++
int largestRectangleArea(vector<int>& h) {
h.push_back(0); // sentinel to flush stack
stack<int> st;
int maxA=0;
for(int i=0;i<h.size();i++) {
while(!st.empty()&&h[i]<h[st.top()]) {
int height=h[st.top()]; st.pop();
int width=st.empty() ? i : i-st.top()-1;
maxA=max(maxA, height*width);
}
st.push(i);
}
return maxA;
}
// Time: O(n) Space: O(n)
#901Online Stock SpanMedium
For each daily stock price, find the span (consecutive days ≤ today's price going backwards).
Pattern: Monotonic decreasing stack of (price, span). When today's price ≥ top, pop and accumulate span. Push (today, span).
C++
class StockSpanner {
stack<pair<int,int>> st; // (price, span)
public:
int next(int price) {
int span=1;
while(!st.empty()&&st.top().first<=price) {
span+=st.top().second;
st.pop();
}
st.push({price,span});
return span;
}
};
// Amortized O(1) per call
#85Maximal RectangleHard
Given binary matrix, find largest rectangle of 1s.
Pattern: Build histogram heights row by row (height[j] = consecutive 1s above including this row). Then apply #84 histogram on each row's heights.
C++
int largestRectInHisto(vector<int>& h) {
h.push_back(0); stack<int> st; int mx=0;
for(int i=0;i<h.size();i++) {
while(!st.empty()&&h[i]<h[st.top()]) {
int ht=h[st.top()]; st.pop();
int w=st.empty()?i:i-st.top()-1;
mx=max(mx,ht*w);
}
st.push(i);
}
h.pop_back(); return mx;
}
int maximalRectangle(vector<vector<char>>& mat) {
int m=mat.size(), n=mat[0].size(), mx=0;
vector<int> h(n,0);
for(int r=0;r<m;r++) {
for(int c=0;c<n;c++) h[c]=(mat[r][c]=='0')?0:h[c]+1;
mx=max(mx,largestRectInHisto(h));
}
return mx;
}
// Time: O(m*n) Space: O(n)
Recognition cue: "Next greater/smaller element", "previous larger/smaller", "contains stock span", "largest rectangle", "buildings that can see each other" — all monotonic stack.
Deeper Understanding
🧠 Under the Hood — why the "nested loop" is O(n)
Charge each pop to the element being popped, not to the loop iteration doing the popping. An element can only be popped once, so all pops across the entire run cost at most n — even if one single iteration pops 10 elements. This amortized accounting is the same argument that makes sliding-window and union-find analyses work, and it's worth being able to state precisely in an interview.
⚖️ When to Use / When NOT to Use
✅ Use when every element needs its nearest greater/smaller neighbor (either side)
One pass, O(n), and the stack invariant hands you the answer at pop time.
✅ Use when computing per-element "span" or "contribution" ranges (stock span, subarray minimums)
The pop boundary tells you exactly how far an element's dominance extends.
❌ Avoid when you need the max/min of arbitrary ranges, not nearest neighbors
Instead: sparse table or segment tree — monotonic stacks only answer nearest-boundary questions.
❌ Avoid when the array is being mutated between queries
Instead: a balanced BST / segment tree; the stack's precomputation assumes a fixed array.
🚫 Common Misconceptions
"A while inside a for makes it O(n²)"
Count operations per element, not per iteration: one push and at most one pop each → ≤ 2n total. The worst single iteration can be O(n), but the sum over all iterations is still O(n).
"Increasing vs decreasing stack doesn't matter"
It's the whole design decision: next greater needs a decreasing stack (pop smaller), next smaller needs an increasing stack (pop bigger). Getting it backwards silently returns wrong neighbors.
"Store values in the stack"
Store indices — you almost always need the distance (span, width, rectangle extent), and the value is one lookup away anyway.
🎤 Interview Follow-ups
"How does Largest Rectangle in Histogram use this?"
For each bar, the nearest smaller bar on each side bounds the widest rectangle with that bar's height. An increasing stack finds both bounds at pop time: area = height[popped] × (right − left − 1).
"Sum of Subarray Minimums — where's the stack?"
The contribution technique: each element is the minimum of (left span × right span) subarrays, where spans come from nearest-smaller boundaries. Careful with ties — use strict on one side, non-strict on the other, to avoid double counting.
"Handle a circular array (Next Greater Element II)?"
Iterate 2n times with index i % n, but only record answers during the first pass and never re-push in the second. Same amortized O(n).