Thirteen LeetCode problems, three of them rated Hard, and a single sentence that decides all of them. This post works through Joseph Choi’s stack session deck in C++ and tries to answer the question the problem tags never answer: not which data structure, but when does an entry stop being useful?
Every solution here was compiled with -fsanitize=undefined,address and checked against a brute-force implementation on tens of thousands of random inputs before it went into the post. Where the deck’s code has a latent trap, I say so and show the version I would submit.
The one idea
In all thirteen problems the stack is not really a container. It is a list of unfinished business: things you have already walked past that are still waiting for something to happen. A ( is waiting for its ). A number in a Reverse Polish expression is waiting for an operator. A histogram bar is waiting for a shorter bar to tell it where its rectangle ends.
So the design question in each problem is the same, and it is a question about deletion rather than insertion:
What fact, when I learn it, proves that an entry in the stack can never matter again?
Answer that and the code writes itself: push everything, and pop while the answer is “this one is now provably useless.” The whole pattern is a rule for throwing things away at the right moment. The three parts below are three answers to that question, in increasing order of how much each pop tells you.
Part 1: when the stack just holds what is still open
Start with the easy case. Why last-in-first-out, and not a queue or a plain counter?
Because in all four problems below, the thing that resolves an item is always the nearest unresolved item, and “nearest” in a left-to-right scan means “most recent.” That is nesting, and LIFO — last in, first out, meaning the most recently added item is the first one you take back out — is exactly the discipline that models nesting. An entry becomes useless the moment its partner shows up.
Valid Parentheses (LC 20, Easy)
Push every opener. On a closer, the only bracket that is allowed to match it is the most recent unmatched opener — anything else means the brackets cross, like ([)]. So there are exactly three ways to fail: the stack is empty when a closer arrives, the top is the wrong kind of opener, or the stack is not empty when the string ends.
bool isValid(string s) {
static const unordered_map<char, char> match{{')', '('}, {']', '['}, {'}', '{'}};
stack<char> open;
for (char c : s) {
auto it = match.find(c);
if (it == match.end()) { open.push(c); continue; } // an opener
if (open.empty() || open.top() != it->second) return false;
open.pop();
}
return open.empty();
}The deck writes the match check as a chain of three || clauses, which is perfectly correct and, on a whiteboard, probably faster to write. The lookup table above scales better if an interviewer adds <> to the alphabet, and it makes the “is this an opener?” test a single find instead of a second chain. Both are O(n) time and O(n) space, the space being the run of unmatched openers.
One detail worth keeping: the open.empty() test has to come before open.top(). Calling top() on an empty std::stack is undefined behaviour, not an exception — on a string like ")" it will happily read whatever is at that address. C++ gives you no seatbelt here.
Evaluate Reverse Polish Notation (LC 150, Medium)
Reverse Polish Notation puts the operator after its operands, so 2 1 + 3 * means (2 + 1) * 3. The point of the notation is that it needs no parentheses, and the reason it needs none is that a stack can evaluate it in one pass: numbers wait, operators consume the two most recent waiters and push one result back.
int evalRPN(vector<string>& tokens) {
stack<int> holder;
for (const string &token : tokens) {
if (token.size() > 1 || isdigit(token[0])) { holder.push(stoi(token)); continue; }
int right = holder.top(); holder.pop(); // second operand first
int left = holder.top(); holder.pop();
switch (token[0]) {
case '+': holder.push(left + right); break;
case '-': holder.push(left - right); break;
case '*': holder.push(left * right); break;
default: holder.push(left / right); break; // truncates toward zero
}
}
return holder.top();
}The only place people lose this problem is operand order. The stack hands you the operands in reverse, so the first value you pop is the right operand. Get it backwards and + and * still pass, because addition and multiplication are commutative (order does not change the result), while - and / quietly produce nonsense. The deck’s helper makes this explicit by assigning number.second first and number.first second; I prefer naming them left and right so the ordering is self-documenting.
Two things the constraints are quietly doing for you. First, the problem says integer division truncates toward zero, which is what C++ does natively since C++11 — -7 / 2 is -3, not -4 — so no correction code is needed. Second, the promise that every intermediate result fits in a 32-bit integer is load-bearing: without it, INT_MIN / -1 is undefined behaviour, and so is INT_MIN negated. If you ever adapt this code outside LeetCode, evaluate into long long.
The token test also matters. Checking token.size() > 1 || isdigit(token[0]) handles negative numbers such as "-11", which are two characters long. A naive test like token != "+" && token != "-" && ... works too, but token[0] == '-' alone does not: it cannot tell the operator - from the number -11.
Simplify Path (LC 71, Medium)
A Unix path is a nesting problem in disguise. Each directory name is an open frame; .. closes the most recent one. . and empty segments (from //) resolve to nothing at all and can be dropped as they arrive.
string simplifyPath(string path) {
vector<string> parts;
string token;
stringstream ss(path);
while (getline(ss, token, '/')) {
if (token.empty() || token == ".") continue;
if (token == "..") { if (!parts.empty()) parts.pop_back(); continue; }
parts.push_back(token);
}
string result;
for (const string &p : parts) result += "/" + p;
return result.empty() ? "/" : result;
}Note that this “stack” is a std::vector, and that is the right call, not a shortcut. The final answer needs the segments in bottom-to-top order to build the string, and std::stack deliberately gives you no way to iterate. When you need stack discipline plus ordered access, reach for a vector with push_back and pop_back. This shows up again in Buildings With an Ocean View below.
The edge cases are all in the rules rather than the algorithm. .. at the root is a no-op, so /../ is /. Runs of periods that are not exactly . or .. are ordinary names, so /.../a/../b/c/../d/./ simplifies to /.../b/d. And because the loop skips empty tokens, getline splitting on / handles leading, doubled, and trailing slashes without any special casing.
Min Stack (LC 155, Medium)
This one is the pivot between Part 1 and Part 2, because it asks a new question: not “what is still open” but “what was true when this element arrived.”
The requirement is O(1) for getMin, which rules out scanning and rules out recomputing after a pop. The insight is that the minimum of the stack is a function of the stack’s state, and every state the stack will ever return to is a state it has already been in. So record the answer for that state while you are in it.
class MinStack {
stack<pair<int, int>> st; // {value, min of everything at or below this point}
public:
MinStack() {}
void push(int val) {
int currMin = st.empty() ? val : min(st.top().second, val);
st.push({val, currMin});
}
void pop() { st.pop(); }
int top() { return st.top().first; }
int getMin() { return st.top().second; }
};Each entry carries the minimum of everything at or below it. pop then needs no work at all: removing the top exposes the entry below, which already knows the minimum of its own prefix. This is the whole trick — a running aggregate stored per element, so that undoing a push automatically undoes the aggregate.
The obvious complaint is space: two integers per element, even when the minimum barely changes. The alternative keeps a second stack that only records new minima:
class MinStack2 {
stack<int> st, mins;
public:
void push(int val) { st.push(val); if (mins.empty() || val <= mins.top()) mins.push(val); }
void pop() { if (st.top() == mins.top()) mins.pop(); st.pop(); }
int top() { return st.top(); }
int getMin() { return mins.top(); }
};On mostly-increasing input this is much smaller. On strictly decreasing input every push is a new minimum and you are back to two integers per element, so the worst case is unchanged. Note the <= in the push: it is not stylistic, and the misfits section shows exactly what breaks without it.
Part 2: why the stack has to be sorted
The waste that ordering removes
Take Daily Temperatures (LC 739): for each day, how many days until it gets warmer? The brute force is a nested loop — for each i, walk right until you find something bigger. That is O(n²), and with n up to 105 it is too slow. But look at why it is slow. It is not that the work is hard; it is that the same elements get scanned again and again, and most of those scans were doomed from the start.
Here is the observation that kills the waste. Suppose you are scanning from the right, and you are standing at index i. Some earlier candidate t sits to the right of i, and nums[t] <= nums[i]. Then t is finished forever: for any index j < i, the element at i stands between j and t, and it is at least as big as nums[t]. So if t would have qualified as j‘s next greater element, i qualifies too — and i is closer. t can never be the answer for anything again.
Discard every such t and what remains is, automatically, sorted: the values from the top of the stack downward are strictly increasing. That is the whole content of the phrase monotonic stack — “monotonic” just means the values only move one way as you walk down the stack. The ordering is not something you maintain on purpose; it is a side effect of throwing away everything that has been proven useless.
Here is the shape, as a standalone function. Once you can write this from memory, nine of the thirteen problems in this post are variations on it:
// previousSmaller[i] = index of the nearest element left of i whose value is
// strictly smaller than a[i]; -1 when there is none.
vector<int> previousSmaller(const vector<int>& a) {
int n = a.size();
vector<int> answer(n, -1);
stack<int> st; // indices; values strictly increasing
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] >= a[i]) // top can never answer for anything further right
st.pop();
answer[i] = st.empty() ? -1 : st.top(); // whatever survived is the nearest one
st.push(i);
}
return answer;
}The four decisions
Every monotonic stack problem is that loop plus four choices. Getting them explicit is most of the work of solving a new one.
| Decision | How to settle it |
|---|---|
| Direction of travel | Scan away from the side the answer lives on, so candidates are already in the stack when you need them — or scan toward it and resolve elements as you pop them. Both work; see LC 739 for the same problem written each way. |
| Which way the values are ordered | Looking for something greater? Keep values decreasing from the bottom, so the top is the smallest and the first survivor of the popping is the nearest bigger one. Looking for something smaller (all the width problems)? Keep them increasing. |
| Strict or non-strict pop | Ask what equal values mean in this problem. “Strictly warmer” means equal temperatures must be popped; “less than or equal” in Online Stock Span means equal prices must be popped too, but for the opposite reason. See strictness. |
| Values or indices on the stack | Indices, unless you are certain no distance or width is ever needed. arr[idx] recovers the value for free; a value cannot recover its index. |
Why it is O(n) and not O(n²)
A nested while inside a for looks quadratic, and the first time you see it, the O(n) claim feels like a cheat. It is not. Each index is pushed exactly once and popped at most once, so the total number of pops across the entire run is bounded by the number of pushes, no matter how the inner loop is distributed. That is an amortised bound — meaning the cost is O(1) per element on average over the whole run, even though one individual iteration might pop thousands of entries.
Instrumenting the Largest Rectangle loop at n = 100,000 makes it concrete. Ascending input, descending input, a sawtooth, and random input all produce exactly 100,001 pushes and 100,000 pops, and between 100,000 and 200,000 comparisons — never more than about 2n, whatever the shape of the data:
| Input shape (n = 100,000) | Pushes | Pops | Comparisons |
|---|---|---|---|
| Strictly descending | 100,001 | 100,000 | 100,000 |
| Strictly ascending | 100,001 | 100,000 | 199,999 |
| Sawtooth (alternating high/low) | 100,001 | 100,000 | 150,000 |
| Uniform random | 100,001 | 100,000 | 199,976 |
Space is O(n) and the worst case is real: a strictly monotonic input never pops anything until the end, so the stack holds every element.
Online Stock Span (LC 901, Medium)
I like starting the monotonic problems here rather than with Next Greater Element, because the “throw it away” step is impossible to miss: this problem hands you a stream and dares you to keep the history.
The span of today is the number of consecutive days, ending today and counting backwards, whose price was at most today’s. Brute force stores every price and walks backward on every call: O(n) per call, O(n²) over 104 calls.
The deck’s framing is the useful one. If today’s price is at least the price on top of the stack, that day is swallowed by today’s span, and so is everything that day had already swallowed. You do not need the individual prices — only the count. So absorb the top’s count into yours, drop the entry, and repeat.
class StockSpanner {
stack<pair<int, int>> spans; // {price, how many days that price already absorbed}
public:
StockSpanner() {}
int next(int price) {
int currSpan = 1;
while (!spans.empty() && spans.top().first <= price) {
currSpan += spans.top().second;
spans.pop();
}
spans.push({price, currSpan});
return currSpan;
}
};Each entry is a price plus the number of days it accounts for, and currSpan accumulates those counts as it eats through the stack. What survives on the stack is a strictly decreasing sequence of prices, which is exactly the set of days that could still block a future span. Amortised O(1) per call, O(n) space.
The pop test is <=, and it must be. With three identical prices of 100, the spans are 1, 2, 3 — each day’s price is “less than or equal” to the next day’s, so each new day absorbs all the earlier ones. Change the test to < and equal prices survive on the stack, blocking the absorption: the same three days return 1, 1, 1. That is the kind of one-character error that passes the sample test case and fails on submission.
Next Greater Element I (LC 496, Easy)
Two arrays, with nums1 a subset of nums2. Brute force is O(n·m): for each value in nums1, find it in nums2 and walk right. The fix is to stop treating the query array as the driver. Answer the question for every position of nums2 in one pass, store the answers, then read them off.
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> nextGreater;
stack<int> st;
for (int i = (int)nums2.size() - 1; i >= 0; --i) {
while (!st.empty() && st.top() <= nums2[i]) st.pop();
nextGreater[nums2[i]] = st.empty() ? -1 : st.top();
st.push(nums2[i]);
}
vector<int> result;
result.reserve(nums1.size());
for (int num : nums1) result.push_back(nextGreater[num]);
return result;
}Scanning right to left, the stack holds the candidates that are still alive — strictly decreasing from the bottom up, so the top is the smallest survivor and therefore the nearest element bigger than everything already discarded. Total cost O(n + m).
The hash map is keyed by value, not index, which works only because the problem guarantees the arrays contain distinct integers. That guarantee is doing more work than it looks like; see the misfits section.
Daily Temperatures (LC 739, Medium)
Same question as LC 496, different output: the distance to the next greater element rather than its value. That one word changes the payload on the stack from values to indices.
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, 0);
stack<int> st; // indices, temperatures strictly decreasing
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && temperatures[st.top()] <= temperatures[i]) st.pop();
if (!st.empty()) answer[i] = st.top() - i;
st.push(i);
}
return answer;
}The deck stores pair<int, int> of temperature and index. Storing only the index and reading temperatures[st.top()] is equivalent and halves the memory; with a bounded value range like 30–100 the pair is not wrong, just unnecessary. Either way, the essential change from LC 496 is that indices are now mandatory, because st.top() - i is the answer.
This problem is also the cleanest place to see that the direction of travel is a free choice. Scan forward instead, and the roles invert: the stack holds days that are still waiting for a warmer day, and each pop resolves an older day rather than answering the current one.
vector<int> dailyTemperaturesForward(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, 0);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
answer[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return answer;
}Both versions passed 20,000 randomised comparisons against brute force. The forward version has a small practical advantage: it needs no sentinel and no cleanup pass, because answer is pre-filled with zeros and anything left on the stack at the end is correctly a zero. Which one you write should come down to which invariant you can state out loud under interview pressure — “the stack holds candidates” or “the stack holds unanswered questions.”
Next Greater Element II (LC 503, Medium)
One array, but circular: the search wraps past the end and back to the front. The trick is to not handle the wrap at all — just walk the array twice and let the modulo do the folding.
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st;
for (int i = 2 * n - 1; i >= 0; --i) {
int idx = i % n;
while (!st.empty() && nums[st.top()] <= nums[idx]) st.pop();
result[idx] = st.empty() ? -1 : nums[st.top()];
st.push(idx);
}
return result;
}The loop runs from 2n - 1 down to 0 and maps each step to i % n. Passing over the second copy first fills the stack with the elements that a wrap-around search would reach; by the time the loop reaches the real indices, every candidate it needs is already there. Writes to result[idx] happen twice for each index, and the second write — from the first copy — is the one that is correct, because only then is the stack complete.
Two passes are enough, and it is worth knowing why rather than taking it on faith. The global maximum of the array has no next greater element and returns -1; every other element finds its answer within one full lap, because the maximum is somewhere in that lap and would qualify. A third pass could add nothing.
The deck pushes values here rather than indices, which is fine because the answer is a value and result[idx] is addressed by the loop variable. I push indices out of habit, for the reason in the decision table: it costs nothing and it survives a follow-up question that asks for a distance.
Buildings With an Ocean View (LC 1762, Medium, Premium)
Note: LC 1762 is a LeetCode Premium problem, so it is only viewable with a paid subscription. The statement is short enough to work from: the ocean is to the right, and a building has a view if every building to its right is strictly shorter. Return the qualifying indices in increasing order.
The deck calls this a straightforward monotonic stack problem, and the framing fits: scan from the right, and a building is blocked exactly when something taller has already been seen. But look at what the code actually needs.
vector<int> findBuildings(vector<int>& heights) {
int n = heights.size();
vector<int> result;
int tallest = -1;
for (int i = n - 1; i >= 0; --i) {
if (heights[i] > tallest) { result.push_back(i); tallest = heights[i]; }
}
reverse(result.begin(), result.end());
return result;
}There is no stack. There is a single int. And that is not a trick — it is a genuine property of this problem, and a good thing to be able to recognise, so it gets its own note in the misfits section below.
Note also the reverse at the end. Scanning right to left produces the indices in descending order, and the problem wants them ascending. The alternative is to scan left to right with a real monotonic stack, popping every building that the current one blocks, which leaves the answers in the right order but does more work. Reversing an O(n) vector once is cheaper than maintaining the stack.
Part 3: one pop, two boundaries
So far a pop has answered one question: “what is the nearest bigger thing?” The four problems left are Hard or nearly Hard, and they all rest on a stronger reading of the same event. When you pop an index, you learn two facts at once:
- The right boundary is the current index
i— it is the first element that triggered the pop, so it is the first element on the right that violates the ordering. - The left boundary is whatever is now on top of the stack — everything between it and the popped index was already popped, so all of it was on the “does not violate” side.
A popped index therefore owns the maximal window
[left + 1, i - 1]in which it is the minimum — the widest stretch where nothing is smaller than it. That single sentence is the whole of Part 3.
The width of that window is i - left - 1, and that expression appears verbatim in the next three solutions. Notice that a value can only be discovered this way at the moment it is popped, which is why these loops do their real work inside the while, not after it.
Sum of Subarray Minimums (LC 907, Medium)
Add up min(b) over every contiguous subarray b. There are about n²/2 subarrays and n goes to 3 × 104, so enumerating them is out.
The deck’s route is the one I find easiest to re-derive at a whiteboard, and it is a dynamic-programming recurrence rather than a counting formula. Group the subarrays by their right endpoint — so every subarray is counted exactly once, by the position where it ends — and define
endingHere[i] = the sum of the minimums of all subarrays that end at index i. There are i + 1 of them, and the answer is the sum of endingHere over all i.
Now let j be the nearest index to the left of i whose value is strictly smaller than arr[i] — precisely what the monotonic stack leaves on top after popping. Split the subarrays [s, i] at j:
- If
s > j, then every element in[s, i]is at leastarr[i]— that is exactly why they were popped — so the minimum isarr[i]. There arei - jsuch subarrays, contributingarr[i] * (i - j). - If
s <= j, thenarr[j]is inside the subarray andarr[j] < arr[i], so extending fromjtoicannot change the minimum. The minimum of[s, i]equals the minimum of[s, j], and summing over all suchsgives back exactlyendingHere[j].
So endingHere[i] = endingHere[j] + arr[i] * (i - j), with endingHere[i] = arr[i] * (i + 1) when the stack empties and there is no smaller element to the left at all.
int sumSubarrayMins(vector<int>& arr) {
const long long MOD = 1000000007;
int n = arr.size();
stack<int> st; // indices, values strictly increasing
vector<long long> endingHere(n, 0); // sum of mins of all subarrays ending at i
long long result = 0;
for (int i = 0; i < n; ++i) {
while (!st.empty() && arr[st.top()] >= arr[i]) st.pop();
long long span = st.empty() ? i + 1 : i - st.top();
if (!st.empty()) endingHere[i] = endingHere[st.top()];
endingHere[i] = (endingHere[i] + (long long)arr[i] * span) % MOD;
result = (result + endingHere[i]) % MOD;
st.push(i);
}
return (int)result;
}One pass, O(n) time, O(n) space. What I like about this formulation is that duplicates need no thought at all: because every subarray is attributed to its right endpoint, nothing can be counted twice, whichever way you break ties. The popular counting formula does not have that property, and the misfits section shows the off-by-double it produces.
I changed the deck’s int accumulators to long long and took the modulo inside the recurrence. The deck’s version is not wrong under LeetCode’s constraints — I ran the worst case and it holds — but it comes within about 12% of overflowing a 32-bit integer, which is closer than I want to be. The arithmetic is in the overflow note.
Largest Rectangle in Histogram (LC 84, Hard)
This is the problem the other two Hards reduce to, so it earns the most attention.
Area is width times height. The height of a rectangle spanning bars [a, b] is the minimum bar in that range, since the rectangle cannot poke above the shortest bar it covers. So the search is over pairs, which is O(n²) — unless you flip the question around. Instead of asking “for each range, what is its minimum?”, ask “for each bar, what is the widest range in which it is the minimum?”
That is the sentence from the start of Part 3, and there are only n bars to ask it about. Every candidate rectangle in the optimal answer is of this form: take the largest rectangle, look at its shortest bar, and the rectangle can be widened until it hits something shorter on each side without losing any height. So the maximum over “each bar in its maximal window” is the true maximum.
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
stack<int> st; // indices, heights strictly increasing
long long maxArea = 0;
for (int i = 0; i <= n; ++i) {
int currHeight = (i < n) ? heights[i] : 0; // sentinel flushes the stack
while (!st.empty() && heights[st.top()] >= currHeight) {
int height = heights[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top(); // first bar strictly shorter on the left
maxArea = max(maxArea, (long long)(i - left - 1) * height);
}
st.push(i);
}
return (int)maxArea;
}Three details carry this solution.
The stack holds indices, not heights. It has to: the width comes from subtracting positions. heights[st.top()] gets the height back whenever it is needed.
The loop runs to i == n, one past the end, with a sentinel height of 0 — a fake value chosen so that it is guaranteed to trigger every remaining pop. Without it, a run of bars that never meets anything shorter (say, an ascending histogram) would sit on the stack at the end of the loop and never get measured, and you would need a separate drain loop with a different width formula. The sentinel makes the flush fall out of the main loop.
The left boundary is -1 when the stack empties, giving a width of i - (-1) - 1 = i, which is correct: nothing to the left is shorter, so the window reaches the front of the array. Using 0 here instead of -1 is the single most common bug in this problem, and it is an off-by-one you will not catch on the sample input.
Trace [2,1,5,6,2,3] and you can see the answer appear at i = 4: the current height 2 pops bar 3 (height 6, width 1, area 6) and then bar 2 (height 5, left boundary 1, width 4 - 1 - 1 = 2, area 10). Bar 2’s window is exactly [2, 3] — the pair of tall bars — and 10 is the answer.
Maximum Score of a Good Subarray (LC 1793, Hard)
Score is min(nums[i..j]) * (j - i + 1) — the same area expression as the histogram — with one extra rule: the subarray must contain a given index k. The deck’s read is that this is LC 84 with a filter, and that read is exactly right.
int maximumScore(vector<int>& nums, int k) {
int n = nums.size();
stack<int> st;
long long ans = 0;
for (int i = 0; i <= n; ++i) {
int val = (i < n) ? nums[i] : 0;
while (!st.empty() && nums[st.top()] >= val) {
int height = nums[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top();
if (left + 1 <= k && k <= i - 1) // the window must contain k
ans = max(ans, (long long)(i - left - 1) * height);
}
st.push(i);
}
return (int)ans;
}The only new line is the containment test. A popped index owns the window [left + 1, i - 1], so it is a legal candidate precisely when left + 1 <= k <= i - 1; otherwise skip it and keep going.
Why filtering rather than restricting the scan is safe is worth a sentence, because it is the step most write-ups skip. Take the optimal good subarray and widen it, as in LC 84, until it hits a strictly smaller element on each side. The minimum does not drop, the width does not shrink, and k is still inside — a wider window cannot lose a point it already contained. So the optimum is always one of the maximal windows the stack enumerates, and testing each one for containment is enough.
A subtlety about equal values: when several equal elements are popped in sequence, each pop reveals a left boundary further to the left, so the windows get wider as the run is consumed. The widest one is measured last and contains all the narrower ones, so if k falls inside a narrow window it falls inside the wide one too. Ties cannot cause a miss. I checked this against brute force on 8,000 random arrays built from values 1–5, which is dense enough that duplicate runs occur constantly.
The well-known alternative is two pointers: start at [k, k] and repeatedly extend toward whichever neighbour is larger. It is shorter and O(n) too. I still prefer the stack version in an interview, because it is the same code as LC 84 and LC 85, and one template you can write cold beats three clever tricks you half-remember.
Maximal Rectangle (LC 85, Hard)
Largest rectangle of 1s in a binary matrix. Hard, and almost no new ideas needed — the work is all in the reduction.
For each row, treat that row as the ground line of a histogram: the bar at column j is the number of consecutive 1s directly above and including matrix[i][j]. Any rectangle of 1s with its bottom edge on row i is then a rectangle in that histogram, and every rectangle has a bottom edge on some row. So run LC 84 once per row and keep the best.
int maxAreaInRow(const vector<int>& heights) {
int n = heights.size();
stack<int> st;
long long maxArea = 0;
for (int i = 0; i <= n; ++i) {
int currHeight = (i < n) ? heights[i] : 0;
while (!st.empty() && heights[st.top()] >= currHeight) {
int h = heights[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top();
maxArea = max(maxArea, (long long)(i - left - 1) * h);
}
st.push(i);
}
return (int)maxArea;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int rows = matrix.size(), cols = matrix[0].size();
vector<int> heights(cols, 0);
int best = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j)
heights[j] = (matrix[i][j] == '1') ? heights[j] + 1 : 0;
best = max(best, maxAreaInRow(heights));
}
return best;
}The heights update in place, one row at a time: a 1 extends the column’s run by one, a 0 resets it to zero. The deck builds the full rows × cols table first, which is easier to inspect while debugging; rolling a single row of heights forward is the same arithmetic with O(cols) extra space instead of O(rows × cols). Total time is O(rows × cols), because each row costs O(cols) in the histogram routine.
Note the input is vector<vector<char>> and the entries are the characters '0' and '1', not the numbers 0 and 1. Comparing against 1 instead of '1' compiles cleanly and silently treats every cell as a zero.
The thirteen problems on one page
| Problem | On the stack | Order kept | Pop while | Scan | A pop means |
|---|---|---|---|---|---|
| 20 Valid Parentheses | Openers | — | closer matches top | → | a pair is complete |
| 150 Evaluate RPN | Operands | — | operator arrives | → | two operands are consumed |
| 71 Simplify Path | Directory names | — | token is .. | → | go up one level |
| 155 Min Stack | {value, min so far} | — | caller says so | — | the previous minimum is restored |
| 901 Online Stock Span | {price, days absorbed} | decreasing | price <= today | stream | absorb that day’s count |
| 496 Next Greater I | Values | decreasing | top <= nums2[i] | ← | that candidate is dead |
| 739 Daily Temperatures | Indices | decreasing | temp[top] <= temp[i] | ← | that candidate is dead |
| 503 Next Greater II | Indices, two laps | decreasing | nums[top] <= nums[idx] | ← | that candidate is dead |
| 1762 Ocean View | Nothing (one int) | decreasing | — | ← | — |
| 907 Subarray Minimums | Indices | increasing | arr[top] >= arr[i] | → | the DP chain link is exposed |
| 84 Largest Rectangle | Indices | increasing | h[top] >= curr | → | that bar’s maximal window is known |
| 1793 Good Subarray | Indices | increasing | nums[top] >= val | → | same, then test it contains k |
| 85 Maximal Rectangle | Indices, per row | increasing | h[top] >= curr | → per row | same as LC 84 |
Reading down the “pop while” column is the fastest way to internalise the pattern. Everything above the line is a partner arriving; everything below it is a proof of obsolescence.
Misfits, edge cases, and the things that bite
This is the part the tutorials skip. Everything below was verified by running it, not by reasoning about it.
Strict or non-strict: where it actually changes the answer
“Should the pop test be > or >=?” is the most common source of one-character bugs in this pattern, and the honest answer is that it depends on the problem — in some it flips the result, in others both work. Randomised testing tells you which is which. I ran each variant against brute force on 20,000 arrays of length 1–8 drawn from a tiny value range, so that duplicates were everywhere:
| Problem | Pop on equal | Pop only on strict | Verdict |
|---|---|---|---|
| 739 Daily Temperatures | 0 failures | 13,373 failures | Must pop on equal |
| 901 Online Stock Span | 0 failures | fails on [100,100,100] | Must pop on equal |
| 84 Largest Rectangle | 0 failures | 0 failures | Either works |
| 907 Subarray Minimums | 0 failures | 0 failures | Either works |
The split is not arbitrary. In LC 739 the question is “strictly warmer,” so an equal temperature is not an answer; leave it on the stack and it will be reported as one. Concretely, [30, 30] returns [1, 0] instead of [0, 0]. LC 901 is the mirror image: the span counts days “less than or equal” to today, so equal prices must be absorbed, and [100, 100, 100] returns 1, 1, 1 instead of 1, 2, 3.
In LC 84 and LC 907 both tests work, for different reasons. In LC 84 the leftmost bar of a run of equal heights eventually measures the full width, so a narrower measurement taken earlier is harmless — it is dominated by the wider one. In LC 907 each subarray is attributed to its right endpoint, so the accounting cannot double up. The rule I would carry into an interview: decide the strictness from the wording of the problem, then test the tie case explicitly — [5, 5] or [2, 2, 2] costs ten seconds and catches it.
The counting formula for LC 907 needs asymmetric strictness
The solution most often posted for LC 907 is not the DP recurrence above but a counting argument: arr[i] is the minimum of (i - L[i]) * (R[i] - i) subarrays, where L is the previous smaller index and R the next smaller. Sum arr[i] times that count and you are done.
It is a good formula with a trap in it. If you use “strictly smaller” on both sides, then with equal values every element in a tied run claims the subarrays that span the run, and the sum comes out too high. On [2, 2] the correct answer is 6 and the symmetric version returns 8. Across 20,000 random arrays, symmetric strictness failed 14,569 times; making one side “smaller or equal” failed zero times.
Which side gets the equality is arbitrary as long as you pick one — it is the tie-break that decides which element of a run owns a shared subarray. The DP version in the main solution sidesteps the whole question, which is why I prefer teaching it first.
Store indices unless you are certain you will never need a width
arr[idx] turns an index into a value in one character. Nothing turns a value back into an index. LC 496 and LC 503 can store values because their answers are values; the moment a problem asks “how many days” or “how wide,” values are a dead end and the rewrite is not local. Storing indices by default costs nothing and makes the follow-up question free.
What makes a sentinel valid
A sentinel is a fake extra element whose only job is to flush the stack at the end of the loop. For it to work it has to be guaranteed to trigger the pop test against every real value, which means it has to sit strictly outside the data’s range in the direction the test cares about — or sit at the boundary with a non-strict test.
That distinction matters in LC 84, where heights[i] can legitimately be 0. A sentinel of 0 flushes a zero-height bar only because the test is >=. Switch to > and zero bars survive the flush — harmless here, since their area is zero, but only by luck. LC 1793 is cleaner: nums[i] >= 1, so 0 is genuinely below the range. If a problem allows negative values, a 0 sentinel is simply wrong and you want INT_MIN or an explicit drain loop after the main one.
Unsigned arithmetic on size()
vector::size() returns an unsigned type. Two patterns in the deck’s code sit right on top of that, and both are worth being able to spot on sight.
// as printed in the deck
int tallest = heights.back();
for (int i = heights.size() - 2; i >= 0; --i) { /* ... */ }
// with one building, heights.size() - 2 is computed in size_t:
// heights.size() - 2 == 18446744073709551615
// and only the narrowing to int rescues it, giving i = -1.With a single building, heights.size() - 2 is evaluated in size_t and wraps to 18,446,744,073,709,551,615. Only the narrowing conversion into int saves the loop, producing -1 so the body never runs. That narrowing is well defined in C++20 and implementation-defined before it, so the code passes today and is not something to rely on. Write int n = heights.size(); once and loop on n.
The second pattern is the loop bound in LC 84, LC 1793, and LC 85:
for (int i = 0; i <= heights.size(); ++i) { ... } // warning: -Wsign-compare
// i is converted to size_t before the comparison, so a negative i would
// become a huge positive number: (-1 <= heights.size()) is false.This one works, because i is never negative, but it warns under -Wall and it is the same mechanism that makes -1 <= heights.size() evaluate to false. Any code that mixes a possibly-negative index with size() is one refactor away from an infinite loop or an out-of-bounds read. The same one-line fix removes all three warnings.
How close these solutions run to 32-bit overflow
Two of the deck’s solutions accumulate into int and stay inside the range only because of the specific constraints. Neither is a bug on LeetCode; both are worth knowing about, because the same code with slightly larger limits is silently wrong.
| Problem | Largest value an int must hold | Share of INT_MAX |
|---|---|---|
907, result + endingHere[i] before the modulo | 1,900,000,006 | 88% |
1793, (i - left - 1) * nums[idx] | 2,000,000,000 | 93% |
For LC 907 the worst case is n = 30,000 with every element at the maximum 30,000: the un-reduced sum for a single position reaches 900,000,000, and adding a modulus that can be as large as 1,000,000,006 brings the total to 1.9 billion against a ceiling of 2,147,483,647. For LC 1793, an array of 100,000 copies of 20,000 with k = 0 produces a score of exactly 2,000,000,000 — the intended answer, and 93% of the way to the ceiling. Both ran clean under the undefined-behaviour sanitizer, so the margin is real rather than lucky. I still moved both to long long, because the cost is nothing and the failure mode is a wrong answer with no crash.
LC 1762 does not need a stack at all
The deck files Buildings With an Ocean View under monotonic stacks, and conceptually that is right. But the code needs one int, and understanding why is more useful than the problem itself.
A monotonic stack collapses to a single variable exactly when you only ever consult its extreme element and never need the ones underneath. Scanning from the right, a building is blocked if anything to its right is at least as tall — that is a question about the maximum so far, nothing else. The stack’s lower entries encode “what would block you if the tallest thing were removed,” and nothing in this problem ever removes it.
Contrast with LC 739, where days are popped one at a time and the entries below genuinely get consulted later. The test to apply to a new problem: does anything ever un-block an element? If not, a running maximum or minimum is the whole answer, and reaching for the stack is over-engineering. It is also a nice thing to notice out loud in an interview.
The hash map in LC 496 depends on a guarantee
nextGreater is keyed by value, which is only meaningful because LC 496 promises the arrays hold distinct integers. Drop that promise and the map keeps one answer per value — with a right-to-left scan, the leftmost occurrence’s — while the problem would no longer have a single well-defined answer per value anyway. If a variant allows duplicates, the answer has to be indexed by position, which means a vector of size m rather than a map.
There is a second, quieter hazard in the read-out loop. nextGreater[num] uses operator[], which inserts a default-constructed 0 for a missing key rather than failing. Because nums1 is guaranteed to be a subset, no key is ever missing — but if that guarantee broke, the bug would surface as the plausible-looking answer 0 rather than a crash. at() throws instead, and in code you do not control the inputs to, that is the safer default.
The two-stack Min Stack must record ties
In the space-saving variant, the push test is val <= mins.top(). Make it strict and the structure breaks on the shortest possible input: push 2, push 2, pop. With <, the second 2 is not recorded; the pop then sees st.top() == mins.top() and removes the minimum anyway, leaving mins empty while st still holds a 2. The next getMin() reads the top of an empty stack, which is undefined behaviour — in my test build it returned garbage rather than crashing, which is the worst of both worlds.
The deck’s pair version has no equivalent hazard, since every element carries its own answer. That is a real argument for the “wasteful” version: it has fewer states in which it can be wrong.
When a monotonic stack is the wrong tool
The pattern is seductive once it clicks, so it is worth knowing its edges.
- Elements leave from both ends. Sliding Window Maximum (LC 239) looks like a monotonic stack problem and is not: the window’s left edge expires elements that no comparison would ever pop. You need a double-ended queue (a
deque, which can push and pop at both ends), and the giveaway is any fixed-size window. - The array changes between queries. A monotonic stack is a single sweep that answers every position once. Interleave updates with “what is the next greater element now?” and the sweep is invalidated; that is a segment tree or a balanced tree, not a stack.
- You need the second-nearest, not the nearest. “Second Greater Element” (LC 2454) needs two stacks in sequence — elements popped from the first graduate into the second — because one stack can only resolve one event per element.
- The comparison is not a total order. The discard argument rests on transitivity: if
xbeatsyandybeatsz, thenxbeatsz. Under a comparison where that fails — multi-criteria dominance, for instance — the popped element may not really be obsolete and the pattern silently loses answers.
How to practise this
Thirteen problems is a lot of code to hold in your head, and you do not need to. What transfers is one loop and four decisions.
- Write the
previousSmallerskeleton from memory until it is automatic, including the-1case. - For a new problem, say out loud what the stack holds and what makes an entry obsolete. If you cannot finish that sentence, the pattern is probably not the answer.
- Settle the four decisions explicitly before typing: direction, ordering, strictness, payload.
- Test the tie case and the single-element case by hand. Between them they catch most of the bugs in this post.
- In order: LC 20 → 496 → 739 → 901 → 503 → 907 → 84 → 1793 → 85. LC 84 is the hinge; the last two are corollaries of it.
Credit and the rest of the series
The problem selection, the ordering, and the framing of each problem come from Joseph Choi‘s stack session deck, including the two observations that make the hardest problems tractable: reading LC 1793 as Largest Rectangle with a filter, and reducing LC 85 to one histogram per row. The C++ here is my own, rewritten where I preferred different types or a different invariant, and every listing was compiled and differentially tested before publication.
Other pattern write-ups in this series: Cycle Sort, Prefix Sum, and Decrease and Conquer.