Interactive Lab · DSA & Algorithms
A stack does two things: push onto the top and pop off the top. That's all, and it's enough to crack a whole family of interview problems. Part 1: check whether brackets are balanced, the most-asked stack question there is. Part 2 is the pattern that separates good candidates from great ones: the monotonic stack. To find each element's next greater element, the obvious answer scans ahead from every position, O(n²). Instead, keep a stack of elements still waiting for an answer; when a bigger value arrives, everyone smaller pops off, answered. Each element goes on once and comes off at most once, so the whole thing is O(n).
▶ Part 1, balanced brackets: push the openers, pop on the closers
Each opener ( [ { is pushed. Each closer must match the opener on top of the stack, which is popped. A closer with an empty stack or the wrong top, or openers left over at the end, means unbalanced.
▶ Part 2, the monotonic stack: next greater element in one pass
Scan left to right. The stack holds indices still waiting for something bigger, and their values always decrease from bottom to top (that's the "monotonic" part). When the current value beats the top, the top pops and gets its answer, and we check the new top. Then the current index is pushed to wait.
Stacks are everywhere a program has to remember "what's still open": your browser's back button, undo in an editor, the call stack that runs recursion, and every compiler and JSON parser checking that brackets close. The monotonic stack is a top placement pattern: Next Greater Element, Daily Temperatures, Stock Span, Largest Rectangle in Histogram and Trapping Rain Water are all the same idea. Spotting "for each element, find the nearest bigger/smaller one" and answering "monotonic stack, O(n), because each element is pushed and popped at most once" is exactly what interviewers at product companies listen for.
The code that's actually running, the highlighted line is the current step
In Part 2, load the staircase down preset: 9 8 7 6 5 4 3 2 1 10. Nothing gets an answer until the last element, and then nine pops happen in a single step. That looks like the worst case for "O(n)". Predict: across the whole run, how many total pushes and pops happen for these 10 numbers, and how many comparisons would the brute-force "scan ahead from every index" approach make? Jump to the end and read the counters.
The takeaway
while inside a for, but each index is pushed exactly once and popped at most once, so the total work is at most 2n. This "amortized" argument is the answer interviewers want when they ask "isn't that O(n²)?".a[j]) and the distance (i − j), which is how Daily Temperatures turns the same code into "days until warmer".