Stack Problems

Six classic interview problems — Valid Parentheses, Min Stack, Evaluate Reverse Polish Notation, Daily Temperatures, Car Fleet and Largest Rectangle in Histogram — solved from zero with one tool: a pile where you only ever touch the top. For each problem you will see the slow obvious idea, why a stack fixes it, the pseudocode, the Dart code, and an animation you can feed your own input, with the input and the stack drawn side by side. By the end you will recognise the three stack patterns (matching pairs, evaluating, and the monotonic stack) and be able to explain why a loop that pops inside a loop is still O(n).

What a stack is and the three stack patterns

Some words first:

• A stack is a collection where you may only touch one end, called the top. It is also called LIFO: Last In, First Out.
• Push means "put a new item on top". Pop means "take the top item off and get it back". Peek means "look at the top item without removing it".
• O(1) ("order one") means the work does not grow with the size of the input; O(n) means it grows in step with the input size n; O(n²) means twice the input gives four times the work. See C03 · Growth of Functions.

Dart's List is already a stack

Dart has no separate Stack class, and it does not need one. A growable List where you use the end of the list as the top is a perfect stack:

Why the end and not the front? The items of a List sit side by side in memory. Adding or removing at the end moves nothing else. Adding or removing at the front (insert(0, x), removeAt(0)) shifts every other item by one place — O(n) each time. "Amortized O(1)" for add means: once in a while the list runs out of room and copies itself into a bigger block, but because the block doubles, the copying averages out to a constant amount per add. That is explained with pictures in D26 · List methods (growth and amortised O(1)); stacks built from scratch are in C10 · Stacks and queues.

The three stack patterns

Almost every stack interview question is one of these three shapes. Learn to spot them and the code nearly writes itself.

1. Matching pairs. Something opens, something later closes it, and the most recent thing that opened must be the first to close — brackets, HTML tags, function calls. Push when something opens; pop and compare when something closes. (Valid Parentheses.)
2. Evaluating and undoing. Keep results you are not ready to use yet. In Reverse Polish Notation, numbers wait on the stack until an operator needs the last two. In an editor, every action is pushed so that "undo" pops the most recent one. (Evaluate RPN, Min Stack.)
3. The monotonic stack. "For every item, find the next item to its right that is bigger (or smaller)." Keep a stack of items that are still waiting for their answer. Their values only go one way from bottom to top — that is what monotonic means (always falling, or always rising). When a new item arrives, it is the answer for every waiting item it beats, so those are popped. (Daily Temperatures, Car Fleet, Largest Rectangle.)

Here is the monotonic stack on its own — "next greater element": for each number, the first bigger number to its right, or −1 if there is none.

Why a loop that pops inside a loop is still O(n)

The code above has a while inside a for, which usually smells like O(n²). Count the stack operations instead of the loops. Each index is pushed exactly once (the last line of the for). Once an index is popped it is gone for good, so it is popped at most once. The while loop can only pop what was pushed, so over the whole run all the while loops together do at most n pops — no matter how they are spread out. One step may pop five items and the next step none. In total: at most 2n stack operations, O(n). This way of counting the total instead of the worst single step is called amortized analysis — the same argument as the multipop example in C17 · Amortized Analysis. The push and pop counters in the animation show it live.

You have met this idea before: Sliding Window Maximum in Step 13.3 · Sliding Window Maximum kept a monotonic deque — the same "pop the items that can never win again" rule. A deque was needed there because old items also expired from the front. Here nothing expires, so a stack (one open end) is enough.

Valid Parentheses

The task. You get a string s made only of the six characters ( ) [ ] { }. Return true if the brackets are correctly matched: every opener is closed by the same kind of closer, the closers come in the reverse order of their openers (inner pairs close before outer ones), and no closer appears without an opener before it. Otherwise return false. The empty string counts as valid.

Brute force. Find any adjacent matching pair — (), [] or {} — and delete it. Repeat until nothing changes. The string was valid exactly when nothing is left. Each round scans the whole string, and there can be n/2 rounds: O(n²).

Key insight. When a closer arrives, it must match the most recent opener that is still open. "Most recent still open" is exactly the top of a stack of openers. So: push every opener; on a closer, pop the top and check that it is the right kind. Counting is not enough — ")(" and "{[}]" have balanced counts but are invalid.

Why it is correct. The stack always holds the openers that are still open, in the order they were opened, with the newest on top. A closer is legal only if it closes the newest one, and popping removes exactly that opener. At the end, anything still on the stack was opened and never closed.

An edge case: every closer matches, but one opener is never closed. The loop finishes without any mismatch, and only the final check stack is empty catches it.

Complexity. Time O(n) — each character is pushed at most once and popped at most once. Space O(n) — in the worst case (all openers, like "((((") every character waits on the stack.

Follow-ups interviewers ask. Only one kind of bracket: a counter is enough (the stack's height is all that matters) — the fewest insertions to fix such a string (p04-q4), the deepest nesting (p04-q11), the fewest deletions (p04-q19) and the longest valid piece (p04-q21). Brackets mixed with other text: ignore every other character. HTML-like tags: push the tag name, compare names on a closing tag.

The idea underneath: stacks built from scratch in C10 · Stacks and queues, using the List methods of D26 · List methods.

Min Stack

The task. Design a stack of whole numbers with four operations, each in O(1) time: push(x) puts x on top, pop() removes the top item, top() returns the top item, and getMin() returns the smallest item currently in the stack. You may assume pop, top and getMin are only called when the stack is not empty.

Brute force. A plain stack, and getMin looks at every item. Push, pop and top are O(1), but getMin is O(n).

Key insight. The minimum of a stack can only change in two ways: a push can lower it, and a pop can restore an older minimum. A pop never creates a brand new minimum — it can only go back to one that existed before. So remember, for every level of the stack, the minimum of everything at or below that level. Keep a second stack mins next to values: when x is pushed, push min(x, top of mins) onto mins. Pop both stacks together. Then getMin is just the top of mins.

Why it is correct. The invariant (a fact that is true after every operation): mins[i] is the smallest of values[0..i]. A push makes it true for the new top because the smallest of "everything below plus x" is min(x, mins[i − 1]). A pop removes the top level only, and every lower mins entry was about values that are all still there. The same two-stack idea can store pairs instead: one stack of (value, minSoFar) records.

An edge case: the same minimum pushed several times. Because mins gets an entry on every push, each copy has its own partner, and popping one copy keeps the minimum correct.

Complexity. Time O(1) for every operation (one or two list operations at the end). Space O(n) — the second stack doubles the memory.

Follow-ups interviewers ask. O(1) extra memory: store a coded value 2x − min whenever the minimum changes (p04-q30). A max stack (flip the comparison). A queue with O(1) getMin: build it from two min stacks, the same way p04-q2 builds a queue from two stacks. Undo/redo history (p04-q12).

The idea underneath: a stack carrying extra facts per level — the same "remember the answer so far" idea as the running minimum in Step 13.3 · Best Time to Buy and Sell Stock.

Evaluate Reverse Polish Notation

The task. In Reverse Polish Notation (RPN, also called postfix) the operator comes after its two operands: 3 4 + means 3 + 4, and 3 4 + 2 * means (3 + 4) × 2. No brackets are ever needed. You get the expression as a list of tokens (each token is a whole number such as "12" or "-7", or one of "+" "-" "*" "/"). Return its value. Division between two whole numbers truncates toward zero (drop the fractional part: 7 / 2 = 3 and −7 / 2 = −3). The expression is always well-formed and never divides by zero.

Brute force. Find the first operator in the list. The two tokens just before it must be its operands. Replace those three tokens with the result, and start scanning again from the beginning. Each step is O(n) and there are up to n/2 steps: O(n²).

Key insight. In postfix, an operator always uses the two values produced most recently — and "most recent" means a stack. Push numbers. On an operator, pop twice, compute, push the result. The first pop is the right operand b (it was pushed last) and the second pop is the left operand a; then compute a op b. For + and × the order does not matter, but for − and / it does: "5 9 -" is 5 − 9 = −4, not 9 − 5.

Division in Dart — exactly. The integer division operator ~/ truncates toward zero: it computes the exact quotient and drops the fractional part. So -7 ~/ 2 is -3 and 7 ~/ -2 is -3, which is exactly what this problem wants. (Careful: unary minus binds tighter than ~/, so -7 ~/ 2 means (-7) ~/ 2.) This is different from floor division, which rounds down: Python's -7 // 2 is −4, and Dart's (-7 / 2).floor() is also −4. And Dart's % is never negative (-7 % 2 is 1), while remainder keeps the sign ((-7).remainder(2) is −1). Dividing an int by zero with ~/ throws an IntegerDivisionByZeroException.

An edge case: a negative number divided by a positive one, where truncating and rounding down give different answers.

Complexity. Time O(n) — one push or two pops plus a push per token. Space O(n) — in an expression like 1 2 3 4 + + + all the numbers wait on the stack before any operator comes.

Follow-ups interviewers ask. Evaluate a normal (infix) expression with brackets: one stack of saved partial results is enough for + and − (p04-q20); add × and ÷ with their higher priority (p04-q27). Convert infix to postfix: the "shunting-yard" algorithm keeps a stack of operators waiting for their operands. Decode nested repeat patterns like 3[a2[c]] (p04-q15), the same "save the outer state, work on the inner one" idea.

The idea underneath: the call stack of D07 · Functions & the Call Stack works the same way — a function's arguments are pushed, the function uses the most recent ones, and its result is handed back to whoever is waiting.

Daily Temperatures

The task. temps[i] is the temperature on day i. For every day, return how many days you must wait after it until a strictly warmer day. If no warmer day ever comes, return 0 for that day.

Brute force. For each day, walk forward until a warmer day. If temperatures keep falling, every walk goes to the end: O(n²).

Key insight. This is "next greater element" with a twist: we want the distance, so the stack stores day indexes, not temperatures. Keep a stack of days that are still waiting for a warmer day. Their temperatures never rise from bottom to top (a monotonic decreasing stack) — because if a warmer day had come after a waiting day, that waiting day would already have been popped. When day day arrives, pop every waiting day that is colder: for each one, today is its first warmer day, so it waited day − colder days. Then push today.

Why popping is safe. A popped day has its final answer — the first warmer day is the earliest one, and nothing later can beat "today". And a day that stops the popping (warmer or equal) is also not answered by anything we skipped: every day below it on the stack is at least as warm, so today cannot be warmer than them either.

An edge case: temperatures only fall. Nothing is ever popped, every day waits on the stack until the end, and every answer stays 0.

Complexity. Time O(n) — every day is pushed once and popped at most once (the counting argument from the opening section). Space O(n) — in a falling week every day is on the stack at the same time. If temperatures only rise, the stack never holds more than one day.

Follow-ups interviewers ask. The "next bigger value" itself instead of the distance (p04-q7). The list is circular — after the last day comes the first again (p04-q13: loop twice). Look backwards instead: how many days in a row up to today were not warmer than today — the stock span (p04-q8). Temperatures only between 30 and 100: you can also scan from the right and keep, for each temperature, the next day it appears — O(n · 71).

The idea underneath: the monotonic stack of the opening section, and the same pop-what-can-never-win rule as the deque in Step 13.3 · Sliding Window Maximum.

Car Fleet

The task. n cars drive along a single-lane road toward the same target mile. Car i starts at mile position[i] (all different, all before the target) and drives at speed[i] miles per hour. A car can never pass the car in front of it: if it catches up, it slows down and drives right behind it at the slower speed. Cars driving together like that form a fleet. A car that catches up exactly at the target also joins that fleet. A single car is a fleet too. Return how many fleets arrive at the target.

Brute force. A car starts its own fleet exactly when it needs more time than every car ahead of it (otherwise it catches up with whichever fleet arrives last among those ahead). Check every car against every car ahead: O(n²).

Key insight. Sort the cars by position, closest to the target first. Walk through them in that order, keeping a stack of fleet arrival times; the top is the fleet just ahead of the current car. Compute the car's alone time (target − position) ÷ speed. If it is bigger than the top, the car can never catch that fleet: push its time — a new fleet. Otherwise it catches the fleet ahead at or before the target and arrives with it: push nothing. The answer is the stack's size. The stored times only rise from bottom to top — another monotonic stack.

Why only the top matters. The fleet just ahead is the slowest to arrive of everything ahead (every fleet further ahead arrives sooner — that is why they are separate). If the car cannot catch the fleet right in front of it, it cannot catch any fleet beyond it either.

An edge case: every car needs exactly the same time. Each car "catches up" exactly at the target, which counts as joining, so the stack holds a single fleet.

Complexity. Time O(n log n) for the sort; the stack pass is O(n). Space O(n) for the order and the stack. In this problem the stack only ever grows, so a single variable "slowest arrival so far" would do — the stack makes the fleets visible and carries over to harder versions.

Follow-ups interviewers ask. When does each car catch the car ahead (collision times)? Scan from the front with a stack of cars that are still "free", popping cars that will crash into someone else before they can be caught. Rocks moving left and right that destroy each other on contact (p04-q14) — the same "what does the newcomer do to the top of the stack?" loop.

The idea underneath: sorting first (C02 · Insertion & Merge Sort, and Dart's sort with a compare function from D26 · List methods), then a monotonic stack.

Largest Rectangle in Histogram

The task. A histogram is a row of bars of width 1 standing side by side; heights[i] is the height of bar i. Return the area of the largest rectangle that fits completely inside the bars. The rectangle must sit on the ground and cover a run of neighbouring bars, so its height is limited by the shortest bar it covers.

Brute force. Try every run of bars i..j, keeping the running minimum height while j grows: O(n²).

Key insight. Keep a stack of bar indexes whose heights rise from bottom to top (a monotonic increasing stack). A bar on the stack is still "growing to the right" — nothing lower has come yet. When bar i arrives and is lower than the top bar, the top bar's rectangle cannot reach i: pop it and measure it now.

The width, carefully. When bar t (height tall) is popped at step i:

• Its right wall is i: bar i is lower than tall. Every bar between t and i is at least as tall as t: the ones still above t on the stack are (the stack rises), and any that left earlier were popped by lower bars that are themselves above t.
• Its left wall is left = the index on top of the stack after popping t. Every bar that stood between left and t was popped by t itself or by a bar that t popped later — and a bar is only ever popped by a lower bar — so all of them are taller than t. If the stack is empty, no bar on the left is lower, and left = −1 (an imaginary wall just before index 0).
• So the rectangle covers bars left + 1 to i − 1: width = i − left − 1, area = tall × width.

The sentinel. Bars still on the stack when the list ends never met a lower bar on their right. Instead of writing a second loop for them, pretend there is one extra bar of height 0 at index n. It is lower than every real bar (or equal to a bar of height 0, whose area is 0 anyway), so it pops everything that is left, with i = n as their right wall. A made-up item like this, added only to remove a special case, is called a sentinel.

An edge case: all bars the same height. Nothing pops until the sentinel arrives; then the bars are popped from the right, and each one measures a wider rectangle than the last: widths 1, 2, 3, 4.

Complexity. Time O(n) — every index (and the sentinel) is pushed once and popped at most once. Space O(n) — when the heights rise all the way, the whole list sits on the stack.

Follow-ups interviewers ask. The largest rectangle of 1s in a grid of 0s and 1s: build a histogram for each row and run this function on it (p04-q22). The sum of the minimum of every subarray — each value counts once for every subarray where it is the smallest, which needs exactly the left and right walls computed here (p04-q23). Water trapped between bars, solved layer by layer with a stack (p04-q25).

The idea underneath: two "next smaller element" answers from one monotonic stack (the opening section), and the two-pointer view of the same bars in Step 13.2 · Trapping Rain Water and Container With Most Water.

Quiz

Interview questions

Variations and follow-ups of the six problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow reference.

Cheat sheet

Each index is pushed once and popped at most once, so a monotonic stack is O(n) even with a while inside the for. If items must also leave from the old end (a window that slides), use a deque instead (Step 13.3 · Sliding Window Maximum).