07 — Stack & Monotonic Stack

What a stack is and when you want one

A stack is last-in-first-out: you add and remove from the same end, like a stack of plates.

Reach for one whenever the most recently seen unresolved thing is the one you must deal with first. That describes two distinct families:

1. Matching / nesting — brackets, expressions. The most recent unclosed bracket is the one a ) must match.
2. Monotonic stacks — "next greater element", spans, histograms. The stack holds items still waiting for an answer, and an arriving element resolves several at once.

Use ArrayDeque, not java.util.Stack (02).

Family 1 — matching and evaluation

Valid Parentheses

"([{}])" is valid; "([)]" is not.

Why a stack is the right structure: when you meet a closing bracket, it must match the most recent unclosed opener. "Most recent" is exactly what a stack gives you.

Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');

for (char c : s.toCharArray()) {
    if (pairs.containsValue(c)) {          // an opener
        stack.push(c);
    } else {                                // a closer
        if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
    }
}
return stack.isEmpty();

Trace on "([)]":

Two failure modes, and candidates routinely handle only one:

1. A closer arrives with an empty stack — ")" alone. Caught by stack.isEmpty().
2. Openers are left over at the end — "((". Caught by the final stack.isEmpty().

Name both out loud.

Evaluate Reverse Polish Notation

RPN writes operators after operands: "2 1 + 3 *" means (2 + 1) * 3 = 9.

Why RPN exists: it's unambiguous without parentheses, and it evaluates with a stack in one pass. Push numbers; on an operator, pop the two most recent numbers, combine, push the result back.

Deque<Integer> stack = new ArrayDeque<>();
for (String tok : tokens) {
    switch (tok) {
        case "+" -> stack.push(stack.pop() + stack.pop());
        case "*" -> stack.push(stack.pop() * stack.pop());
        case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); }
        case "/" -> { int b = stack.pop(), a = stack.pop(); stack.push(a / b); }
        default  -> stack.push(Integer.parseInt(tok));
    }
}
return stack.pop();

Trace on ["2","1","+","3","*"]:

Answer: 9. ✓

The operand-order trap. For + and * order doesn't matter. For - and / it does:

// tokens: ["5", "2", "-"]  means 5 - 2 = 3
int b = stack.pop();    // b = 2  (pushed LAST, popped FIRST)
int a = stack.pop();    // a = 5
stack.push(a - b);      // 5 - 2 = 3    ✓

// stack.pop() - stack.pop() would give 2 - 5 = -3    ✗

The second pop is the left operand. This is the most common bug in the question — and writing a and b as named variables rather than inlining the pops is what prevents it.

Min Stack

Support push, pop, top, and getMin, all in O(1).

The naive getMin scans the stack: O(n). The fix: store the running minimum alongside each value.

private Deque<int[]> stack = new ArrayDeque<>();   // {value, minAtOrBelowThisPoint}

public void push(int val) {
    int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
    stack.push(new int[]{val, min});
}
public void pop()   { stack.pop(); }
public int top()    { return stack.peek()[0]; }
public int getMin() { return stack.peek()[1]; }

Trace — push 5, 3, 7, 2:

getMin() → 2. After one pop(), the top is {7, 3} and getMin() → 3 — the previous minimum is restored automatically, because each entry carries the answer that was correct when it was pushed.

That's the elegance: no recomputation on pop, ever.

Alternative: a second stack holding only minima, pushing when val <= currentMin. Saves space but needs care — you must push on <=, not <, or duplicate minima get lost when one is popped. Mention both; the paired-value version is harder to get wrong under pressure.

Family 2 — the monotonic stack

The mental model

This is the hardest idea in the section, so build it slowly.

The problem: given temperatures = [73, 74, 75, 71, 69, 72, 76, 73], for each day, how many days until a warmer one?

Brute force: for each day, scan forward until you find something bigger. O(n²).

The observation: when you're at day 5 (72°) and you look back, days 4 (69°) and 3 (71°) are both still waiting for a warmer day. And 72° answers both at once. Even better — day 3 (71°) is "blocked" by nothing useful, because anything that would warm day 4 also comes after day 3.

The realization: if a day is followed by a warmer day, the earlier cooler one becomes irrelevant for future queries — anything warmer than the recent day is automatically warmer than it too.

So: keep a stack of days still waiting for an answer, and keep it in decreasing temperature order. When a warm day arrives, it resolves every waiting day it beats — pop them all.

The two orientations

How to choose: ask "what event finally lets me answer for an element I already passed?" That event is the pop trigger, and it determines the orientation.

Template — next greater element

int[] res = new int[n];
Arrays.fill(res, -1);                        // -1 = nothing greater to the right
Deque<Integer> stack = new ArrayDeque<>();   // holds INDICES; their values decrease

for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        int idx = stack.pop();
        res[idx] = nums[i];                  // nums[i] is idx's answer
    }
    stack.push(i);
}

Store indices, not values. You almost always need the position or distance, and the value is one lookup away.

Daily Temperatures — the same template

int[] res = new int[temperatures.length];
Deque<Integer> stack = new ArrayDeque<>();

for (int i = 0; i < temperatures.length; i++) {
    while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
        int idx = stack.pop();
        res[idx] = i - idx;                  // DISTANCE, not value
    }
    stack.push(i);
}
return res;                                  // unresolved indices keep 0

Full trace on [73, 74, 75, 71, 69, 72, 76, 73]:

Result: [1,1,4,2,1,1,0,0]. ✓

Notice step 5: one arriving element resolved two waiting days. That's the saving.

Why it's O(n), not O(n²)

The nested while looks quadratic. It isn't, and this is the most-asked follow-up in the section:

"Each index is pushed exactly once and popped at most once. So across the entire outer loop, the inner while body runs at most n times in total. Total work is O(n) — the pushes and pops are bounded in aggregate, not per iteration."

Some single iterations pop five elements; then five later iterations pop nothing. It averages out. This is the amortized/aggregate argument from 01.

Largest Rectangle in Histogram

The hardest stack problem in the 150. Worth over-preparing.

heights = [2, 1, 5, 6, 2, 3] → largest rectangle area is 10 (heights 5 and 6, width 2).

The idea

For each bar, the largest rectangle using that bar's full height extends left and right until it hits something shorter. So for each bar you need: how far left and right can I extend before hitting a shorter bar?

Maintain an increasing stack of (startIndex, height). When a shorter bar arrives, every taller bar on the stack can no longer extend right — settle it now.

Deque<int[]> stack = new ArrayDeque<>();   // {startIndex, height}, heights increasing
int best = 0;

for (int i = 0; i < heights.length; i++) {
    int start = i;
    while (!stack.isEmpty() && stack.peek()[1] > heights[i]) {
        int[] top = stack.pop();
        best = Math.max(best, top[1] * (i - top[0]));   // settle: height × width
        start = top[0];        // THIS bar can extend back to where the taller one began
    }
    stack.push(new int[]{start, heights[i]});
}

// Bars that never met a shorter bar extend all the way to the end
for (int[] rem : stack) {
    best = Math.max(best, rem[1] * (heights.length - rem[0]));
}
return best;

Trace on [2, 1, 5, 6, 2, 3]:

Final drain: {0,1} → 1×(6−0)=6; {2,2} → 2×(6−2)=8; {5,3} → 3×(6−5)=3.

Best = 10. ✓

The one line that matters: start = top[0]

When bar i pops a taller bar, bar i inherits that bar's starting position. Why: a rectangle of height heights[i] can span backward across everything that was taller than it — those bars are all tall enough to contain it.

Look at i = 4 (height 2) in the trace. It popped bars starting at index 3 and 2. So a rectangle of height 2 can start from index 2, not index 4. Without this line, the algorithm silently under-counts.

The final drain loop

Bars still on the stack at the end never met a shorter bar, so they extend to the right edge — width is length - start. A strictly increasing histogram like [1,2,3] never pops anything during the main loop, and this loop is what finds its answer.

An alternative is appending a sentinel 0 bar to force a full drain, trading the second loop for an array copy.

If Maximal Rectangle comes up, it's this algorithm run once per row over a running histogram of column heights.

Trapping Rain Water — the stack view

Fills water in horizontal layers rather than per-column. The two-pointer version (07) is O(1) space and the better answer — know this one as the "I see the monotonic-stack framing too" follow-up.

Deque<Integer> stack = new ArrayDeque<>();   // indices, heights decreasing
int water = 0;

for (int i = 0; i < height.length; i++) {
    while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
        int bottom = stack.pop();            // the floor of this puddle
        if (stack.isEmpty()) break;          // no left wall — water escapes
        int left = stack.peek();             // the left wall
        int width = i - left - 1;
        int depth = Math.min(height[left], height[i]) - height[bottom];
        water += width * depth;
    }
    stack.push(i);
}

Each pop identifies a puddle bounded by left (the new stack top) and i (the arriving bar), with bottom as its floor. The stack.isEmpty() check handles the case where there's nothing to the left to hold water in.

Car Fleet

Not obviously a stack problem — which is the point.

Cars at various positions drive toward a target at various speeds. A faster car catching a slower one joins its fleet and is capped to the slower speed. How many fleets arrive?

The reasoning

1. A car can only be blocked by cars in front of it (closer to the target).
2. So sort by position descending — process the frontmost car first.
3. Each car's arrival time if unobstructed is (target - position) / speed.
4. If a car's time is greater than the fleet ahead's, it's slower and arrives later → it forms a new fleet.
5. If its time is less than or equal, it catches up and is absorbed → not a new fleet.

int n = position.length;
int[][] cars = new int[n][2];
for (int i = 0; i < n; i++) cars[i] = new int[]{position[i], speed[i]};
Arrays.sort(cars, (a, b) -> b[0] - a[0]);      // DESCENDING by position

Deque<Double> stack = new ArrayDeque<>();      // arrival times of fleet leaders
for (int[] car : cars) {
    double time = (double) (target - car[0]) / car[1];
    if (stack.isEmpty() || time > stack.peek()) {
        stack.push(time);                      // slower than the fleet ahead — new fleet
    }
    // otherwise absorbed; push nothing
}
return stack.size();

Trace: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3].

Sorted descending by position:

Answer: 3 fleets. ✓

Sorting descending is the detail that makes it work. Ascending would evaluate cars before the ones blocking them are known. Getting the direction backwards is the standard failure here.

stack.size() is the answer. A counter would work identically — the stack just makes the "fleet leader" semantics explicit.

Generate Parentheses

Filed under Stack, but it's really backtracking — the stack is the recursion itself. See 15 — Backtracking.

Recognition checklist

Complexity summary