Min Stack (Design Data Structures)
Min Stack is a medium design data structures problem solved with the stack pattern.
The best approach, encoded values (one stack, one min variable), runs in O(1) time and O(n) space.
Below are 2 approaches in Java, from second stack of minimums up.
Problem
Design a stack with push, pop, top and getMin, all in O(1). This is the Design module’s version: go beyond the pair-per-element solution and learn the single-stack encoding trick.
Examples
Example 1
- Input
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()- Output
-3, 0, -2
Constraints
- Every operation in O(1).
- pop, top and getMin are called only on a non-empty stack.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Second stack of minimums | O(1) | O(n) |
| Encoded values (one stack, one min variable) | O(1) | O(n) |
1Second stack of minimums
O(1)O(n)Push onto a min stack only when the value is <= the current minimum; pop from it when the popped value equals the minimum.
- push: stack.push(v); if min empty or v <= min.peek(), min.push(v).
- pop: if stack.pop() == min.peek(), min.pop().
class MinStack {
private final Deque<Integer> st = new ArrayDeque<>(), mins = new ArrayDeque<>();
public void push(int val) {
st.push(val);
if (mins.isEmpty() || val <= mins.peek()) mins.push(val);
}
public void pop() {
if (st.pop().equals(mins.peek())) mins.pop();
}
public int top() { return st.peek(); }
public int getMin() { return mins.peek(); }
}2Encoded values (one stack, one min variable)
O(1)O(n)One stack; no second stack of minimums.Keep min separately. When pushing v < min, push 2v - min (which is below v) and set min = v. On pop, if the top is below min, it was encoded: restore the old min as 2·min - top. The stack stores longs to avoid overflow.
- push: empty → push v, min = v. v >= min → push v. Else push 2v - min; min = v.
- pop: t = pop(); if t < min, min = 2·min - t.
- top: t < min ? min : t.
class MinStack {
private final Deque<Long> st = new ArrayDeque<>();
private long min;
public void push(int val) {
if (st.isEmpty()) { st.push((long) val); min = val; }
else if (val >= min) st.push((long) val);
else { st.push(2L * val - min); min = val; }
}
public void pop() {
long t = st.pop();
if (t < min) min = 2 * min - t;
}
public int top() {
long t = st.peek();
return (int) (t < min ? min : t);
}
public int getMin() { return (int) min; }
}Edge cases to test
- Pushing the current minimum again, then popping one copy
- Values near Integer.MIN_VALUE (the encoding trick needs long)
Hints
Hint 1
Seen in the Stack module with a pair per element. Here, try the O(1)-extra-space version: store an encoded value when a new minimum arrives.
FAQ
What is the best time complexity for Min Stack?
Encoded values (one stack, one min variable) runs in O(1) time and O(n) extra space.
Which pattern does Min Stack use?
It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Design a Stack With Increment Operation, Maximum Frequency Stack.
Is there a brute force solution for Min Stack?
Yes. Second stack of minimums takes O(1) time and O(n) space. Push onto a min stack only when the value is <= the current minimum; pop from it when the popped value equals the minimum.
Which edge cases should I test for Min Stack?
Pushing the current minimum again, then popping one copy; Values near Integer.MINVALUE (the encoding trick needs long).