Stacks:
Two Sessions, Ten Problems

Trigger: "I'm at index i and I need to consult elements I already passed." Rather than a nested backward loop (O(n²)), push as you go; the top of the stack is your most-recent relevant predecessor, reachable in O(1).

• ⭐ TRICK — Push either the index, the value, or the character depending on the problem. Push the index when you need to write back into a result array later (you can always recover the value via arr[index], but not the reverse).
• 💡 TIP — Stack follows LIFO. Core ops all O(1): push, pop, peek/top, size, isEmpty.
• 💡 TIP — The recurring template: for each element → while (!stack.isEmpty() && <condition on top>) pop; then push current. Only the while condition changes per problem. This shape covers ~80% of stack problems.
• ⭐ TRICK — Think conversely. "Next greater element" feels like a forward-looking problem, but you solve it by asking "is the current element the answer for some earlier element still on the stack?" Same mental flip as "I wish I had a parent pointer" in trees.

Given a string of only ()[]{}, decide if brackets are balanced and correctly nested. Valid: "()[]{}" → true. Invalid: "(]" → false.

• Practice: LeetCode 20 — Valid Parenthesesleetcode.com/problems/valid-parentheses
• Pattern family: matching / delimiter balancing — the archetypal stack problem.

Push opening brackets; on a closing bracket, pop and check the match. A closing bracket is only valid if the top of the stack is its exact corresponding opener.

• Opening bracket → push it.
• Closing bracket → if stack empty or popped element ≠ its matching opener → return false.
• End → valid only if the stack is empty (leftover openers mean unbalanced).
• Time O(n), Space O(n).

⚠ PITFALL — A closing bracket arriving when the stack is empty (e.g. ")(") is instantly false. You only push openers, so an early closer has nothing to match. Beginners forget the empty check and crash on pop().

⚠ PITFALL — Don't forget the final return stack.isEmpty(). Matching every closer is not enough; unmatched openers like "(((" must fail.

💡 TIP — A HashMap (closing→opening) is also fine and equally O(n)/O(n); the verdict: for 3 bracket types the switch is cleaner, but a map scales better if you had 50 bracket types. Neither changes complexity — it's a readability/extensibility call, not a performance one.

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for (char ch : s.toCharArray()) {
        switch (ch) {
            case '(': case '{': case '[':
                stack.push(ch);          // opener: just store it
                break;
                case ')':
                if (stack.isEmpty() || stack.pop() != '(') return false;
                break;
                case '}':
            if (stack.isEmpty() || stack.pop() != '{') return false;
                break;
                case ']':
                if (stack.isEmpty() || stack.pop() != '[') return false;
                break;
            }
    }
    return stack.isEmpty();               // leftover openers = invalid
}

Why it matters. This "push open / pop-and-verify on close" skeleton reappears in every delimiter problem — decode string, infix conversion, and any nested-structure parser.

Repeatedly delete two adjacent equal letters until none remain; return the final string. "abbaca" → remove bb → "aaca" → remove aa → "ca". Answer is unique.

• Practice: LeetCode 1047 — Remove All Adjacent Duplicates In Stringleetcode.com/problems/remove-all-adjacent-duplicates-in-string
• Pattern family: collapse-adjacent — same shape as valid-parentheses, comparing against the top.

The stack top is always "the last surviving character." Compare current to top: match → pop (they annihilate); mismatch → push.

• Stack empty or top ≠ current → push current.
• Top == current → pop (cancel the adjacent pair).
• At the end, pop everything and reverse to rebuild the string.
• Time O(n), Space O(n).

⭐ TRICK — A naive "scan, delete a pair, restart" is O(n²) because each deletion can expose a new adjacent pair earlier in the string. The stack makes the newly-exposed neighbor the top automatically, so cascading cancellations are handled in one pass.

⚠ PITFALL — Popping the stack gives characters in reverse order. Fill a char[] from index size-1 down to 0, or reverse a builder — otherwise you return the answer backwards.

public String removeDuplicates(String s) {
    Stack<Character> stack = new Stack<>();
    for (char ch : s.toCharArray()) {
        if (stack.isEmpty() || stack.peek() != ch) stack.push(ch);
        else stack.pop();               // adjacent equal pair cancels
    }
    char[] arr = new char[stack.size()];
    for (int i = stack.size(); i > 0; i--) arr[i - 1] = stack.pop(); // reverse-fill
    return new String(arr);
}

Why it matters. "Compare against the top and cancel" generalizes to asteroid-collision-type problems and any last-write-wins reduction.

Decode k[encoded_string], where the bracketed string repeats k times; brackets can nest. "3[a]2[bc]" → "aaabcbc". "3[a2[c]]" → "accaccacc". k is a positive integer.

• Practice: LeetCode 394 — Decode Stringleetcode.com/problems/decode-string
• Pattern family: nested expansion — two parallel stacks, one for counts, one for partial results.

Keep a running res string plus a count-stack and a result-stack. An [ opens a new scope; a ] closes it by repeating res and gluing it onto the enclosing result.

• Digit → build the full multi-digit number (count = 10*count + (ch-'0')), push to count-stack.
• [ → push current res onto result-stack, reset res = "" (fresh inner scope).
• Letter → append to res.
• ] → pop the enclosing prefix into temp, append res to it count times (pop the count), then res = temp.
• Time O(n) (n = length of decoded output), Space O(n).

⭐ TRICK — On [, resetting res to empty is the key move: it starts a clean buffer for the inner segment. On ], you fold the repeated inner buffer back into the saved prefix, so nested brackets resolve inside-out for free.

⚠ PITFALL — Numbers can be multi-digit (13, 100). You must loop while the char is a digit and accumulate with 10*count + digit; reading a single char breaks on "12[ab]".

💡 TIP — Does one stack suffice? Yes — a single stack of mixed tokens works, but two stacks are kept purely for clarity; complexity is identical either way. [+] The clean single-stack alternative is to push both the count and the prefix as a pair on one stack.

public String decodeString(String s) {
    String res = "";
    Stack<Integer> countStack = new Stack<>();
    Stack<String>  resStack   = new Stack<>();
    int idx = 0;
    while (idx < s.length()) {
        if (Character.isDigit(s.charAt(idx))) {
            int count = 0;
            while (Character.isDigit(s.charAt(idx))) {   // multi-digit
                count = 10 * count + (s.charAt(idx) - '0');
                idx++;
            }
            countStack.push(count);
        } else if (s.charAt(idx) == '[') {
            resStack.push(res);          // save enclosing prefix
            res = "";                    // fresh inner scope
            idx++;
        } else if (s.charAt(idx) == ']') {
            StringBuilder temp = new StringBuilder(resStack.pop());
            int repeatTimes = countStack.pop();
            for (int i = 0; i < repeatTimes; i++) temp.append(res);
            res = temp.toString();       // fold inner back into prefix
            idx++;
        } else {
            res += s.charAt(idx++);      // ordinary letter
        }
    }
    return res;
}

Why it matters. Parallel stacks (one for "how many," one for "what") is the standard tactic for any recursively-nested notation you must expand.

For every element, find the first larger element to its right; -1 if none. [4,5,2,25] → 4→5, 5→25, 2→25, 25→-1.

• Practice: GeeksforGeeks — Next Greater Elementgeeksforgeeks.org/next-greater-element · related: LeetCode 496leetcode.com/problems/next-greater-element-i
• Pattern family: monotonic (decreasing) stack — the general engine behind NGE, previous-greater, next-smaller, etc.

Store indices of elements still waiting for their answer. When the current element beats the value at the top index, it is that index's next-greater — pop and record.

• Init result[] filled with -1.
• For each i: while stack non-empty and input[stack.top] < input[i] → result[stack.pop()] = input[i].
• Push i. Anything left on the stack at the end keeps its default -1.
• Time O(n) — each index pushed and popped at most once; Space O(n).

⭐ TRICK — The mental flip: instead of "for each element scan right for a bigger one" (O(n²)), ask "for the current element, which earlier pending elements does it satisfy?" That inversion is exactly the tree "no parent pointer → think from parent down" trick reused here.

⚠ PITFALL — Two pointers do not work here. A far-right pointer that jumped ahead for 5 can't come back for 2, whose answer sits right beside it. You need the stack to hold multiple pending elements simultaneously.

⭐ TRICK — Push indices, not values. You need the index to write into result[]; from an index you can always fetch the value, but not vice versa.

💡 TIP — A warning: fewer than ~1% of candidates find this in the 2–4 minutes an interview allows if they don't already know the monotonic-stack pattern. This is a "know it cold" problem. It (and previous/next smaller/greater variants) is the whole monotonic-stack family.

public static int[] findNextGreaterElements(int[] input) {
    if (input == null) return input;
    int[] result = new int[input.length];
    Arrays.fill(result, -1);              // default: no greater element
    Stack<Integer> s = new Stack<>();      // holds INDICES, decreasing values
    for (int i = 0; i < input.length; i++) {
        // current element resolves every smaller pending element on top
        while (!s.isEmpty() && input[s.peek()] < input[i]) {
            result[s.pop()] = input[i];
        }
        s.push(i);
    }
    return result;
}

Why it matters. Monotonic stacks power stock-span, daily-temperatures, largest-rectangle-in-histogram, and trapping-rain-water. Master this one shape and the variants are re-skins.

Return the deepest level of nested parentheses. "(1+(2*3)+((8)/4))+1" → 3 (the digit 8 sits inside 3 nested parens).

• Practice: LeetCode 1614 — Maximum Nesting Depth of the Parenthesesleetcode.com/problems/maximum-nesting-depth-of-the-parentheses
• Pattern family: depth tracking — stack size is the depth, but a counter suffices.

On ( push (or increment) and record the running max; on ) pop (or decrement). The peak stack size is the answer.

• Stack version: ( → push, max = Math.max(max, stack.size()); ) → pop. Time O(n), Space O(n).
• [+] Counter version: ( → ++depth; max = Math.max(max, depth); ) → --depth. Time O(n), Space O(1).

⭐ TRICK — You don't actually need a stack. Since every char is a valid paren and you only care about how many are open, a single integer counter replaces it and drops space to O(1). The stack just makes the "depth = size" intuition obvious.

⚠ PITFALL — Update the max on the open bracket (right after incrementing), not on close. Checking only at close, or after decrementing, misses the true peak.

💡 TIP [!] — The stack version has Space O(n); the counter version is also O(1) space. Either is accepted, but mention the O(1) counter in an interview to show you saw the optimization.

// Counter version [+] — O(1) space, preferred
public int maxDepth(String s) {
    int depth = 0, max = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') max = Math.max(max, ++depth);
        else if (c == ')') depth--;
    }
    return max;
}

// Stack version — O(n) space, same idea
public int maxDepthStack(String s) {
    Stack<Character> h = new Stack<>();
    int max = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') { h.push(c); max = Math.max(max, h.size()); }
        else if (c == ')') h.pop();
    }
    return max;
}

Why it matters. Recognizing when a stack degenerates into a counter is a common interview "can you optimize space?" follow-up.

Merge all overlapping intervals and print the non-overlapping result. {1,5},{2,3},{4,6},{7,8},{8,10},{12,15} → {1,6},{7,10},{12,15}.

• Practice: LeetCode 56 — Merge Intervalsleetcode.com/problems/merge-intervals
• Pattern family: sort-then-sweep; the stack top holds the current merged interval.

Sort by start. Then either the current interval clears the top's end (push it) or it overlaps (extend the top's end to the max of the two).

• Sort intervals by begin.
• Stack empty or curr.begin > top.end → non-overlapping → push curr.
• Else overlapping → top.end = max(top.end, curr.end).
• Time O(n log n) (sorting dominates), Space O(n).

⭐ TRICK — You cannot just compare with interval i-1. After several merges the relevant "previous" interval is whatever sits merged on the stack top, not the literal prior array element. The stack always exposes the live merged interval in O(1).

⚠ PITFALL — Sorting by start time is mandatory. Without it, "current start > previous end" is meaningless and overlaps are missed.

💡 TIP [!] — One version uses two separate ifs (no else). It happens to work because a freshly pushed interval has top == curr, so top.end < curr.end is false. Cleaner: use else if so the merge only runs in the overlap branch. Functionally equivalent here, but the else version is what you should write.

💡 TIP — An auxiliary-array idea works too (same O(n) space) but adds bookkeeping; the stack is simpler. This problem is a cousin of the meeting-rooms / minimum-platforms problems.

public static void mergeIntervals(List<Interval> intervals) {
    intervals.sort(Comparator.comparingInt(a -> a.begin));  // sort by start
    Stack<Interval> stack = new Stack<>();
    for (Interval curr : intervals) {
        if (stack.isEmpty() || curr.begin > stack.peek().end) {
            stack.push(curr);                    // no overlap
        } else if (stack.peek().end < curr.end) {// [!] use else-if for clarity
            stack.peek().end = curr.end;         // overlap: extend end
        }
    }
    while (!stack.isEmpty()) System.out.println(stack.pop());
}

Why it matters. Sort-then-stack (keep the live merged item on top) transfers to insert-interval, employee-free-time, and calendar/booking conflicts.

Evaluate a postfix (operator-after-operands) expression. 82/ → 4. 138*+ → 25 (1+8*3). 545*+5/ → 5.

• Practice: LeetCode 150 — Evaluate Reverse Polish Notationleetcode.com/problems/evaluate-reverse-polish-notation
• Pattern family: expression evaluation — operands wait on a stack until their operator arrives.

Push operands. On an operator, pop the top two, apply, push the result. One value remains at the end — the answer.

• Digit → push c - '0'.
• Operator → x = pop(); y = pop(); push y op x.
• Time O(n), Space O(n).

⚠ PITFALL — Operand order matters for - and /. The second pop is the left operand: compute y op x, not x op y. Getting this backwards silently passes on +/* and fails on subtraction/division.

💡 TIP — No precedence/BODMAS logic is needed. Postfix already encodes evaluation order; you never push operators, only values. The brackets some students pictured are just for explanation, not in the input.

⚠ PITFALL [+] — c - '0' only handles single-digit operands. For multi-digit tokens (LeetCode 150 uses space-separated tokens) split on spaces and parse each token instead.

public static int evalPostfix(String exp) {
    if (exp == null || exp.length() == 0) System.exit(-1);
    Stack<Integer> stack = new Stack<>();
    for (char c : exp.toCharArray()) {
        if (Character.isDigit(c)) {
            stack.push(c - '0');          // operand
        } else {
            int x = stack.pop();          // right operand
            int y = stack.pop();          // left operand
            if      (c == '+') stack.push(y + x);
            else if (c == '-') stack.push(y - x);   // order matters
            else if (c == '*') stack.push(y * x);
            else if (c == '/') stack.push(y / x);   // order matters
        }
    }
    return stack.pop();                   // last value = result
}

Why it matters. Postfix eval is the back half of any calculator; pair it with the next problem (infix→postfix) to evaluate ordinary human expressions.

Convert an infix expression (operator between operands) to postfix. (A+B)*(C/D) → AB+CD/*. Input is whitespace-free tokens.

• Practice: GeeksforGeeks — Infix to Postfixgeeksforgeeks.org/convert-infix-expression-to-postfix-expression (Shunting-yard)
• Pattern family: Shunting-yard — operator stack governed by precedence.

Operands append straight to output. Operators wait on a stack; before pushing one, flush all stacked operators of higher-or-equal precedence. Brackets bound sub-scopes.

• ( → push.
• Operand → append to postfix.
• Operator → while stack top has ≥ precedence, pop to output; then push operator.
• ) → pop to output until (, then discard the (.
• End → flush remaining operators to output.
• Time O(n), Space O(n).

⚠ PITFALL — The most-missed step: after the loop ends, drain any operators still on the stack. Skipping this drops trailing operators (e.g. the final *), giving a wrong result.

⚠ PITFALL [!] — A verbal precedence explanation is easy to muddle ("higher priority can sit on top", "bracket has lowest priority"). Trust the code: prec() returns a lower number for higher precedence (*// = 3, +/- = 4), and ( returns Integer.MAX_VALUE so it is never popped by the precedence test. The pop condition is prec(curr) >= prec(top) — pop while the incoming operator is not higher precedence.

💡 TIP — Brackets in infix collectively mark a sub-expression as one operand. If the interviewer guarantees no brackets, delete the two bracket cases; everything else is unchanged.

// LOWER return value = HIGHER precedence
public static int prec(char c) {
    if (c == '*' || c == '/') return 3;      // highest here
    if (c == '+' || c == '-') return 4;
    if (c == '&') return 8;
    if (c == '^') return 9;
    if (c == '|') return 10;
    return Integer.MAX_VALUE;                 // '(' : never popped by prec test
}
public static boolean isOperand(char c) {
    return (c >= 'a' && c <= 'z') || (c>= 'A' && c <= 'Z') || (c>= '0' && c <= '9');
}
public static String infixToPostfix(String infix) {
    if (infix == null || infix.length() == 0) return infix;
    Stack<Character> s = new Stack<>();
    String postfix = "";
    for (char c : infix.toCharArray()) {
        if (c == '(') {
            s.add(c);
        } else if (c == ')') {
            while (s.peek() != '(') postfix += s.pop();   // flush to matching '('
            s.pop();                                       // discard '('
        } else if (isOperand(c)) {
            postfix += c;
        } else {                                           // operator
            while (!s.isEmpty() && prec(c) >= prec(s.peek())) postfix += s.pop();
            s.add(c);
        }
    }
    while (!s.isEmpty()) postfix += s.pop();               // drain remainder
    return postfix;
}

Why it matters. The precedence-driven operator stack (Shunting-yard) is the canonical parser skeleton — it extends to prefix conversion and full expression evaluators.

Return true if two strings are equal after typing into empty editors, where # is a backspace. s="ab#c", t="ad#c" → both become "ac" → true. Backspacing an empty text stays empty.

• Practice: LeetCode 844 — Backspace String Compareleetcode.com/problems/backspace-string-compare
• Pattern family: build-and-compare; optimizable to two-pointer.

Build each string on its own stack — push letters, pop on # (if non-empty) — then compare the two stacks.

• Letter → push. # → pop if the stack isn't empty (guard against empty).
• Compare the two resulting stacks/strings for equality.
• Time O(n), Space O(n).

⚠ PITFALL — Guard the pop: # on an empty stack is a no-op (backspacing empty text stays empty). Popping unconditionally throws.

💡 TIP — A follow-up: a two-pointer scan from the right does it in O(1) space. Walk each string backward, using a "skip" counter to jump over characters cancelled by #. Handling consecutive #s (e.g. "ab##") needs a while loop to accumulate skips before comparing — that's the tricky part reviewers probe.

public boolean backspaceCompare(String s, String t) {
    return build(s).equals(build(t));
}
private String build(String str) {
    Stack<Character> st = new Stack<>();
    for (char ch : str.toCharArray()) {
        if (ch == '#') { if (!st.isEmpty()) st.pop(); }  // guard empty
        else st.push(ch);
    }
    StringBuilder sb = new StringBuilder();
    for (char c : st) sb.append(c);
    return sb.toString();
}

Why it matters. Recognizing that a build-on-stack problem often has an O(1) two-pointer reverse-scan is a frequent interview optimization (also appears in comparing strings with spaces).

Design a stack supporting push, pop, top, and getMin — all in O(1). "Design a stack" means implement the full operation set plus the special getMin.

• Practice: LeetCode 155 — Min Stackleetcode.com/problems/min-stack
• Pattern family: auxiliary-stack design — a parallel stack tracks the running minimum.

Keep a main stack plus an auxiliary stack whose top is always the current minimum. Push to aux only when the new value ≤ current min; pop from aux only when the popped value equals the current min.

• push(v): push to main; push to aux if aux empty or v ≤ aux.peek().
• pop(): pop main; if that value == aux.peek(), also pop aux.
• getMin() → aux.peek(). All operations O(1).

⭐ TRICK — "O(1) minimum" + "only the top is reachable" ⟹ store the minimum at the top of a second stack. The aux stack mirrors the min history so it retreats correctly as you pop.

⚠ PITFALL — Use ≤ (not <) when pushing duplicates of the current min onto aux. If 3,3 are pushed but aux keeps only one 3, popping one 3 would wrongly discard the min. The ≤ keeps a copy per duplicate.

💡 TIP — Student sanity check: push 2,3,4,5 → aux holds only 2. Popping 5 ≠ 2, so aux is untouched; min stays 2. The aux only shrinks when the actual minimum leaves.

class MinStack {
    private Stack<Integer> s   = new Stack<>();  // all elements
    private Stack<Integer> aux = new Stack<>();  // running minimums

    public void push(int val) {
        s.push(val);
        if (aux.isEmpty() || aux.peek() >= val) aux.push(val); // >= keeps dups
    }
    public int pop() {
        int top = s.pop();
        if (top == aux.peek()) aux.pop();        // min leaving -> retreat aux
        return top;
    }
    public int top()      { return s.peek(); }
    public int size()     { return s.size(); }
    public boolean isEmpty() { return s.isEmpty(); }
    public int getMin()   { return aux.peek(); } // O(1)
}

Why it matters. The "parallel aux structure that maintains an invariant (min/max) in O(1)" idea recurs in max-stack, min-queue, and sliding-window-minimum designs.

Problem	Technique	Key insight	Time / Space
Valid Parentheses	Matching stack	Push openers; pop-and-verify on closer; end empty	O(n) / O(n)
Remove Adjacent Duplicates	Collapse-adjacent stack	Top = last survivor; equal→pop, else push	O(n) / O(n)
Decode String	Two stacks (count + result)	[ resets buffer; ] folds repeated inner into saved prefix	O(n) / O(n)
Next Greater Element	Monotonic (decreasing) stack	Invert: current resolves earlier pending indices	O(n) / O(n)
Max Nesting Depth	Depth counter / stack	Peak open-count; counter → O(1) space	O(n) / O(1)
Merge Intervals	Sort + stack	Sort by start; top holds live merged interval	O(n log n) / O(n)
Evaluate Postfix	Evaluation stack	Push operands; operator pops two, order = y op x	O(n) / O(n)
Infix → Postfix	Shunting-yard	Flush ≥-precedence operators before push; drain at end	O(n) / O(n)
Backspace Compare	Build-and-compare / two-pointer	#→pop (guard empty); reverse two-pointer = O(1)	O(n) / O(n)
Min Stack	Auxiliary-stack design	Aux top = min; push on ≤, pop when min leaves	O(1) / O(n)

The through-line. Nine of ten reduce to one question — "do I need an element I already passed?" — and three (max-depth, backspace) reveal a space optimization once you see the stack is doing a counter's or two-pointer's job. The monotonic stack (NGE) is the single highest-leverage pattern to know cold for interviews.

Insight: push openers, pop-&-match on closers, end empty.

TC O(n) · SC O(n)

for ch in s:
  if opener: push
  else: if empty or pop()!=match: false
return stack.empty()

⚠ empty stack on closer → false · must end empty

doodle: [ ( { <-top ] — pop matches from the right

Practice: LeetCode 20 — Valid Parentheses

Insight: top = last survivor; equal→pop, else push.

TC O(n) · SC O(n)

for ch in s:
  if empty or top!=ch: push
  else: pop
reverse-pop -> string

⭐ cascading cancels handled free · ⚠ reverse at end

doodle: a b b <-cancel-> a

Practice: LeetCode 1047 — Remove All Adjacent Duplicates In String

Insight: count-stack + result-stack; [ saves prefix & resets, ] repeats.

TC O(n) · SC O(n)

digit: count=10*count+d
'[': push res; res=""
letter: res+=ch
']': res = pop_prefix + res*pop_count

⚠ multi-digit numbers · ⭐ reset res on [

doodle: cnt[3] res["a"] <- fold on ]

Practice: LeetCode 394 — Decode String

Insight: stack of indices; current resolves smaller pending ones.

TC O(n) · SC O(n)

res[]=-1
for i:
  while stk & input[top]

⭐ think converse · ⭐ push INDEX · ⚠ two-pointer fails

doodle: [4 5 2] <-25 pops 2,then...

Practice: GfG — Next Greater Element · LeetCode 496