Stack

A stack solves problems where you need to process elements in reverse order of arrival, using LIFO ordering to track context at each nesting level with a single O(n) pass.

• Replaces recursive or multi-pass solutions — every element is pushed and popped at most once, so cost is always O(n)
• Three modes: matching and validating pairs, maintaining per-element state (running min, counts), and building results
• Reach for it when you see nested structures, matching pairs, undo operations, or expression evaluation

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of stack patterns.

Practice Tips

How to Identify a Stack Problem

• You need to match or validate pairs (brackets, tags, quotes)
• The problem involves nested structures where inner results affect outer ones
• You need to undo the most recent operation (backspace, collision, rollback)
• You need constant-time access to a running min, max, or count as elements arrive
• The result must be built in reverse order of processing

Stack vs. Other Techniques

Interview Approach

1. Identify the pattern: matching, nested state tracking, or reverse build
2. Decide what to store — raw value, pair [val, metadata], or just index
3. Define the pop condition clearly before coding
4. Check !stack.isEmpty() before every peek() or pop()
5. Ask yourself: should the stack be empty at the end? (yes for validation, no for simulation)

3 Main Patterns

Pattern 1: Matching and Validation

Copy// Push opening brackets; on closing bracket, pop and verify match
Stack<Character> stack = new Stack<>();

for (char c : input.toCharArray()) {
    if (isOpening(c)) {
        stack.push(c);
    } else {
        if (stack.isEmpty() || !matches(stack.pop(), c)) {
            return false;
        }
    }
}
return stack.isEmpty();

Pattern 2: Maintain State with Metadata

Copy// Stack stores pairs or objects to track metadata alongside each element
Stack<int[]> stack = new Stack<>(); // [value, currentMin]

for (int val : input) {
    int minSoFar = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
    stack.push(new int[]{val, minSoFar});
}

Pattern 3: Build Result

Copy// Collect elements on the stack, then drain in order to build the final result
Stack<String> stack = new Stack<>();

for (String part : input.split("/")) {
    if (part.equals("..")) {
        if (!stack.isEmpty()) stack.pop();
    }
    else if (!part.isEmpty() && !part.equals(".")) {
        stack.push(part);
    }
}
// Build from stack bottom-to-top

General Templates

Stack Template

Copypublic ReturnType stackProblem(InputType input) {
    Deque<Type> stack = new ArrayDeque<>(); // preferred over Stack<>

    for (Type element : input) {
        // Pop condition varies by problem
        while (!stack.isEmpty() && shouldPop(stack.peek(), element)) {
            Type popped = stack.pop();
            // process popped
        }
        stack.push(element);
    }

    return buildResult(stack);
}

Problem 1: Valid Parentheses ⭐ MUST DO [B75-20]

Given a string of just (, ), {, }, [, ], determine if it is valid.

Example:

CopyInput:  s = "()[]{}"
Output: true

Input:  s = "([)]"
Output: false

Solution:

Copypublic boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');

    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {                       // closing bracket
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        } else {
            stack.push(c);                              // opening bracket
        }
    }

    return stack.isEmpty();
}

Complexity:

Problem 2: Min Stack ⭐ MUST DO

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1).

Example:

Copypush(-2), push(0), push(-3)
getMin() → -3
pop()
top()    → 0
getMin() → -2

Solution:

Copyclass MinStack {
    private Deque<int[]> stack = new ArrayDeque<>(); // [value, currentMin]

    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]; }
}

Complexity:

Problem 3: Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into a text editor where # means backspace.

Example:

CopyInput:  s = "ab#c",  t = "ad#c"
Output: true   (both become "ac")

Input:  s = "ab##",  t = "c#d#"
Output: true   (both become "")

Solution:

Copypublic boolean backspaceCompare(String s, String t) {
    return process(s).equals(process(t));
}

private String process(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c != '#') {
            stack.push(c);
        }
        else if (!stack.isEmpty()) {
            stack.pop();
        }
    }
    return String.valueOf(stack);
}

Complexity:

Problem 4: Evaluate Reverse Polish Notation

Evaluate an arithmetic expression in Reverse Polish Notation (postfix).

Example:

CopyInput:  tokens = ["2","1","+","3","*"]
Output: 9   →  ((2 + 1) * 3) = 9

Input:  tokens = ["4","13","5","/","+"]
Output: 6   →  (4 + (13 / 5)) = 6

Key Insight:

• Numbers accumulate on the stack. An operator pops two operands and pushes the result.
• For subtraction and division, pop b first, then a — the expression is a op b, not b op a.

Solution:

Copypublic int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (String token : tokens) {
        if (token.equals("+")) {
            stack.push(stack.pop() + stack.pop());
        } else if (token.equals("*")) {
            stack.push(stack.pop() * stack.pop());
        } else if (token.equals("-")) {
            int b = stack.pop(), a = stack.pop();
            stack.push(a - b);
        } else if (token.equals("/")) {
            int b = stack.pop(), a = stack.pop();
            stack.push(a / b);
        } else {
            stack.push(Integer.parseInt(token));
        }
    }

    return stack.pop();
}

Complexity:

Problem 5: Decode String ⭐ MUST DO

Given an encoded string with rule k[encoded_string], return the decoded string.

Example:

CopyInput:  s = "3[a]2[bc]"
Output: "aaabcbc"

Input:  s = "3[a2[c]]"
Output: "accaccacc"

Key Insight:

• Two stacks save the state before entering each [: one for the repeat count, one for the string built so far.
• On ], pop both stacks to restore the outer context, then append the inner string repeated k times.
• This handles arbitrary nesting because each [ pushes a clean slate and each ] restores exactly one level.

Solution:

Copypublic String decodeString(String s) {
    Deque<Integer> countStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder current = new StringBuilder();
    int num = 0;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');             // build multi-digit number
        } else if (c == '[') {
            countStack.push(num);                   // save repeat count
            strStack.push(current);                 // save string so far
            current = new StringBuilder();          // fresh start inside brackets
            num = 0;
        } else if (c == ']') {
            int times = countStack.pop();
            StringBuilder outer = strStack.pop();
            for (int i = 0; i < times; i++) {
                outer.append(current);
            }
            current = outer;                        // restore with inner appended
        } else {
            current.append(c);
        }
    }

    return current.toString();
}

Complexity:

Problem 6: Simplify Path

Given an absolute Unix path, simplify it.

Example:

CopyInput:  path = "/home//foo/"
Output: "/home/foo"

Input:  path = "/a/./b/../../c/"
Output: "/c"

Key Insight:

• Split by / and process each segment: skip empty strings and ., pop for .., push anything else.
• The stack naturally accumulates valid path components in order — join them at the end.

Solution:

Copypublic String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();

    for (String part : path.split("/")) {
        if (part.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else if (!part.isEmpty() && !part.equals(".")) {
            stack.push(part);
        }
    }

    // stack iteration goes top-to-bottom; use ArrayList for bottom-to-top
    List<String> parts = new ArrayList<>(stack);
    Collections.reverse(parts);
    return "/" + String.join("/", parts);
}

Complexity:

Problem 7: Asteroid Collision

Given an array of integers representing asteroids (positive = right, negative = left), return the state after all collisions. Same-direction asteroids never collide.

Example:

CopyInput:  [5, 10, -5]   →  [5, 10]       (−5 destroyed by 10)
Input:  [8, -8]       →  []            (equal — both destroyed)
Input:  [10, 2, -5]   →  [10]          (−5 destroyed by 10)

Key Insight:

• A collision only occurs when the stack top is positive and the incoming asteroid is negative.
• Track whether the incoming asteroid survived with a boolean flag — it may destroy several stack elements before being destroyed itself (or surviving).

Solution:

Copypublic int[] asteroidCollision(int[] asteroids) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (int a : asteroids) {
        boolean alive = true;

        while (alive && a < 0 && !stack.isEmpty() && stack.peek() > 0) {
            int top = stack.peek();
            if (Math.abs(a) > top) {
                stack.pop();                        // a destroys top, keeps going
            } else if (Math.abs(a) == top) {
                stack.pop();                        // mutual destruction
                alive = false;
            } else {
                alive = false;                      // a destroyed by top
            }
        }

        if (alive) {
            stack.push(a);
        }
    }

    int[] result = new int[stack.size()];
    for (int i = result.length - 1; i >= 0; i--) {
        result[i] = stack.pop();
    }
    return result;
}

Complexity:

Problem 8: Remove All Adjacent Duplicates In String II

Given string s and integer k, repeatedly remove k adjacent identical characters until no more removals are possible.

Example:

CopyInput:  s = "deeedbbcccbdaa",  k = 3
Output: "aa"
Trace:  remove "eee" → "ddbcccbdaa"
        remove "ccc" → "ddbdaa" ... wait, remove "ddd" → "aa"

Key Insight:

• Store [char, count] pairs on the stack. When the count reaches k, pop immediately — this triggers cascading removals naturally because the now-adjacent pairs on the stack merge on the next character comparison.
• No second pass needed: the stack always reflects the current valid state.

Solution:

Copypublic String removeDuplicates(String s, int k) {
    Deque<int[]> stack = new ArrayDeque<>(); // [char as int, count]

    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek()[0] == c) {
            stack.peek()[1]++;
            if (stack.peek()[1] == k) {
                stack.pop();  // auto-remove on k
            }
        } else {
            stack.push(new int[]{c, 1});
        }
    }

    StringBuilder result = new StringBuilder();
    for (int[] pair : stack) {
        for (int i = 0; i < pair[1]; i++) {
            result.append((char) pair[0]);
        }
    }
    return result.reverse().toString();
}

Complexity:

Problem 9: Remove K Digits

Given a string representing a non-negative integer, remove k digits to produce the smallest possible number.

Example:

CopyInput:  num = "1432219",  k = 3
Output: "1219"

Input:  num = "10200",  k = 1
Output: "200"

Key Insight:

• Greedy: a larger digit followed by a smaller one always makes the number bigger at that position. So whenever a new digit is smaller than the stack top and removals remain, pop the top (remove it).
• If k removals remain after the full pass, trim from the end (the largest remaining digits).
• Strip leading zeros at the end.

Solution:

Copypublic String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char digit : num.toCharArray()) {
        while (!stack.isEmpty() && k > 0 && stack.peek() > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }

    // Remove remaining k digits from the end (largest ones)
    while (k-- > 0) {
        stack.pop();
    }

    // Build result, skipping leading zeros
    StringBuilder result = new StringBuilder();
    boolean leadingZero = true;
    for (char d : stack) {   // stack iterates bottom-to-top
        if (leadingZero && d == '0') {
            continue;
        }
        leadingZero = false;
        result.append(d);
    }

    return result.length() == 0 ? "0" : result.toString();
}

Complexity:

Problem 10: Validate Stack Sequences

Given two arrays pushed and popped, return true if they represent a valid push/pop sequence on an initially empty stack.

Example:

CopyInput:  pushed = [1,2,3,4,5],  popped = [4,5,3,2,1]
Output: true

Input:  pushed = [1,2,3,4,5],  popped = [4,3,5,1,2]
Output: false

Key Insight:

• Simulate: push each value, then greedily pop whenever the stack top equals the next expected pop value.
• If the sequence is valid, every pushed element gets popped exactly once — the stack is empty at the end.

Solution:

Copypublic boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new ArrayDeque<>();
    int popIdx = 0;

    for (int val : pushed) {
        stack.push(val);
        while (!stack.isEmpty() && stack.peek() == popped[popIdx]) {
            stack.pop();
            popIdx++;
        }
    }

    return stack.isEmpty();
}

Complexity:

Problem 11: Score of Parentheses

Given a balanced parentheses string, compute its score: () = 1, AB = A + B, (A) = 2 * A.

Example:

CopyInput:  "()"      →  1
Input:  "(())"    →  2
Input:  "()()"    →  2
Input:  "(()(())))" →  6

Key Insight:

• Push 0 on ( as a placeholder for the score of the group being opened.
• On ), pop the inner score and the outer score. The contribution is max(2 * inner, 1) — the max handles the base case () where inner = 0.
• This naturally computes nested scores bottom-up.

Solution:

Copypublic int scoreOfParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);  // base score for outermost level

    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(0);              // start new group
        } else {
            int inner = stack.pop();
            int outer = stack.pop();
            stack.push(outer + Math.max(2 * inner, 1));
        }
    }

    return stack.pop();
}

Complexity:

Problem 12: Basic Calculator II

Evaluate a string expression containing non-negative integers and operators +, -, *, / (no parentheses).

Example:

CopyInput:  s = "3+2*2"
Output: 7

Input:  s = " 3/2 "
Output: 1

Key Insight:

• Process each number using the previous operator (not the current one). This lets you handle * and / immediately by modifying the last pushed value, while + and - push the number (or its negative) to defer addition.
• Summing the stack at the end handles all the deferred additions.

Solution:

Copypublic int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int num = 0;
    char op = '+';  // previous operator; default to '+' so first number is pushed

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        }

        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            if (op == '+') {
                stack.push(num);
            }
            else if (op == '-') {
                stack.push(-num);
            }
            else if (op == '*') {
                stack.push(stack.pop() * num);
            }
            else if (op == '/') {
                stack.push(stack.pop() / num);
            }
            op = c;
            num = 0;
        }
    }

    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Matching and Validation

• Input has paired delimiters: brackets, tags, quotes
• You need to confirm all openers are matched in the correct order
• The stack should be empty at the end — any remainder means invalid

Maintain State with Metadata

• You need O(1) access to a running min, max, or count as elements arrive and leave
• Nested structures require you to save and restore state at each level (Decode String, Score of Parentheses)
• Elements interact with their neighbors based on some condition (Asteroid Collision)

Build Result

• You need to construct the answer in reverse processing order
• Greedy choices require removing already-processed elements (Remove K Digits)
• The result depends on surviving elements after a simulation (Simplify Path)

Common Mistakes to Avoid

General Stack Mistakes

1. Using the legacy Stack<> class — use Deque<Type> stack = new ArrayDeque<>() instead (faster, not synchronized)
2. Not checking empty before peek/pop — always guard with !stack.isEmpty() to avoid EmptyStackException
3. Building strings with += in a loop — use StringBuilder; string concatenation is O(n²)

Matching and Validation Mistakes

4. Forgetting the empty check at the end — a leftover opening bracket means invalid; always return stack.isEmpty()
5. Using == to compare Character objects — compare chars with == only on primitives; use .equals() for boxed types

Nested State Mistakes

6. Using one stack for both counts and strings — keep them separate (Decode String); mixing types makes the logic error-prone
7. Off-by-one on ] — pop both stacks and rebuild current from the outer string before appending

Build Result Mistakes

8. Forgetting to handle remaining removals — in Remove K Digits, after the main pass, trim k more from the stack end
9. Leading zeros — after building the digit string, skip leading '0' characters; return "0" if the result is empty
10. Wrong subtraction/division order in RPN — pop b first, then a; the expression is a op b