Min Stack Visualization for Coding Interviews
O(1) getMin via parallel min-stack trick.
Concept
Min Stack is a deceptively small problem with a famous twist: design a stack that supports push, pop, top, and getMin, with every operation in O(1) time. The naive approach either scans the stack for the min on every getMin call, which is O(N), or keeps a single min variable, which works until you pop it and then have no idea what the new min should be. The canonical answer is the twin-stack trick: alongside the main stack that holds the values, keep a second stack that at every level records the min of the main stack up to and including that level. Every push checks against the current min and either duplicates it or records a new lower min; every pop removes one entry from each stack. It is a tiny amount of extra memory in exchange for truly constant-time minimum queries, and the same idea generalizes to any associative min-like operation.
How it works
Maintain two ArrayDeque-backed stacks: a data stack that holds the actual pushed values, and a min stack that holds the running minimum parallel to the data stack. On push(x), push x onto the data stack. Then peek at the min stack: if it is empty, push x onto it as well; otherwise push Math.min(x, minStack.peek()). This guarantees that the top of the min stack is always the minimum of all values currently on the data stack. On pop(), pop from both stacks in lockstep. On top(), return the data stack's peek. On getMin(), return the min stack's peek. Because every operation is a fixed handful of pushes, pops, and peeks, each runs in true worst-case O(1). The space cost is O(N) for the min stack, which is the honest price of O(1) min. A classic optimization compresses the min stack by storing pairs of (value, count) so you only push a new entry when the min strictly decreases, which reduces memory for inputs that frequently tie the current min. Both variants preserve the O(1) guarantee.
Implementation
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
public class MinStack {
private final Deque<Integer> data = new ArrayDeque<>();
private final Deque<Integer> mins = new ArrayDeque<>();
/** Push a value; maintain running min invariant. */
public void push(int x) {
data.push(x);
if (mins.isEmpty() || x <= mins.peek()) mins.push(x);
else mins.push(mins.peek());
}
/** Pop and return top. Keeps mins stack in sync. */
public int pop() {
if (data.isEmpty()) throw new NoSuchElementException("stack is empty");
mins.pop();
return data.pop();
}
/** Peek top of stack. */
public int top() {
if (data.isEmpty()) throw new NoSuchElementException("stack is empty");
return data.peek();
}
/** Current minimum across all pushed-but-not-popped values. */
public int getMin() {
if (mins.isEmpty()) throw new NoSuchElementException("stack is empty");
return mins.peek();
}
public int size() { return data.size(); }
public boolean isEmpty() { return data.isEmpty(); }
/**
* Compressed min stack: push (value, count) only when the min strictly decreases.
* Saves memory when inputs frequently tie the current min. Same O(1) bound.
*/
public static final class Compressed {
private final Deque<Integer> data = new ArrayDeque<>();
private final Deque<int[]> mins = new ArrayDeque<>(); // {minValue, runLength}
public void push(int x) {
data.push(x);
if (mins.isEmpty() || x < mins.peek()[0]) mins.push(new int[]{x, 1});
else if (x == mins.peek()[0]) mins.peek()[1]++;
}
public int pop() {
int v = data.pop();
int[] top = mins.peek();
if (v == top[0]) { if (--top[1] == 0) mins.pop(); }
return v;
}
public int top() { return data.peek(); }
public int getMin() { return mins.peek()[0]; }
}
}Complexity
- Time:
O(1) for push, pop, top, and getMin - Space:
O(N) for twin stack; compressed variant amortized less
Common pitfalls
- Scanning the stack on getMin makes it O(N) and defeats the purpose
- Storing a single min variable: pop invalidates it and you cannot recover the previous min
- Using < instead of <= when deciding whether to push onto the min stack drops ties and yields wrong mins after pops
- Forgetting to pop the min stack in lockstep with the data stack
- Using java.util.Stack for the underlying structure: synchronized and slower than ArrayDeque
- Returning Integer.MIN_VALUE on empty rather than throwing; callers may not detect the error
Key design decisions & trade-offs
- Extra memory vs query cost — Chosen: Twin stack trades O(N) memory for O(1) getMin. The common case expects fast min; the memory cost is predictable and bounded
- Duplicate-mins representation — Chosen: Store duplicates explicitly for simplicity. Easier to reason about correctness; compressed variant optimizes memory at cost of complexity
- Error handling — Chosen: Throw on empty pop/top/getMin. Matches Deque.pop semantics and surfaces programmer errors early
Practice problems
Interview follow-ups
- Max Stack with O(1) peekMax and popMax
- Min Queue built from two min stacks
- Sliding window minimum (same spirit with monotonic deque)
- Design a stack with O(1) increment of the bottom K elements
- Implement Queue using two Stacks (classic companion problem)
Why it matters
Min Stack is a core part of the Stacks & Queues toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".