Min Stack is a design question where you build a stack of your own that can also tell you its smallest value instantly, and it is Day 14 of the Tekraze DSA series. Yesterday we used a stack to match brackets. Today we test whether you can trade a little extra memory for speed, which is a habit interviewers love to see.
Also Read: Day 13, Valid Parentheses shows the stack basics this post builds on.
What is the Min Stack problem?
Design a stack that supports push(val), pop(), top() and getMin(), and every one of them must run in O(1) time. getMin() returns the smallest value currently in the stack. You can assume pop, top and getMin are only called on a non-empty stack. You can also try it on LeetCode, where it is problem 155.
Min Stack example
text
push(-2), push(0), push(-3) getMin() -> -3 pop() top() -> 0 getMin() -> -2
How should you think about it in plain words?
The tricky part is popping. If you keep a single variable for the minimum and you pop that minimum, you no longer know what the next smallest value is.
The fix is to let every item remember the minimum at the moment it was pushed. The stack below an item never changes while that item sits on top, so its saved minimum stays correct. When you pop, the item underneath already knows its own minimum. That is the whole trick.
What does the brute force solution look like?
Use a normal stack and scan every element whenever someone asks for the minimum.
python
class MinStackBrute:
def __init__(self):
self.stack = []
def push(self, val):
self.stack.append(val)
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return min(self.stack)
Time is O(1) for push, pop and top, but O(n) for getMin because it walks the whole stack. Space is O(n) for the items. It works, yet it breaks the O(1) rule the problem asks for.
How do we get the optimal Min Stack solution in O(1)?
Store pairs. Each push saves the value together with the smaller of that value and the minimum stored in the current top. getMin just reads the minimum from the top pair, and pop removes the pair so the one below takes over with its own correct minimum.
A popular variant keeps two stacks, one for values and one for minimums, and only pushes to the second when the new value is less than or equal to its top. It saves memory when many values are larger than the minimum, but the pair version is simpler to get right in an interview.
Every operation runs in O(1) time. Space is O(n), since each item carries one extra number. For a quick refresher on reading these numbers
Min Stack in Java
Java’s ArrayDeque is the usual choice for the underlying stack.
java
import java.util.ArrayDeque;
import java.util.Deque;
class MinStack {
// each entry stores {value, minimum so far}
private final Deque<int[]> stack = new ArrayDeque<>();
public void push(int val) {
int currentMin = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
stack.push(new int[]{val, currentMin});
}
public void pop() { stack.pop(); }
public int top() { return stack.peek()[0]; }
public int getMin() { return stack.peek()[1]; }
}
public class Solution {
static void check(int got, int want) {
System.out.println((got == want ? "PASS " : "FAIL ") + got + " " + want);
}
public static void main(String[] args) {
MinStack s = new MinStack();
s.push(-2); s.push(0); s.push(-3);
check(s.getMin(), -3);
s.pop();
check(s.top(), 0);
check(s.getMin(), -2);
s.push(-2); s.push(-2);
s.pop();
check(s.getMin(), -2);
s.push(5);
check(s.top(), 5);
check(s.getMin(), -2);
}
}
Min Stack in Python
In Python, a plain list works as a stack, and each entry is a tuple of value and minimum.
python
class MinStack:
def __init__(self):
# each entry stores (value, minimum so far)
self.stack = []
def push(self, val):
current_min = min(val, self.stack[-1][1]) if self.stack else val
self.stack.append((val, current_min))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def get_min(self):
return self.stack[-1][1]
s = MinStack()
results = []
s.push(-2); s.push(0); s.push(-3)
results.append((s.get_min(), -3))
s.pop()
results.append((s.top(), 0))
results.append((s.get_min(), -2))
s.push(-2); s.push(-2)
s.pop()
results.append((s.get_min(), -2))
s.push(5)
results.append((s.top(), 5))
results.append((s.get_min(), -2))
for got, want in results:
print("PASS" if got == want else "FAIL", got, want)
Min Stack in Rust
In Rust, a Vec of tuples does the job.
rust
struct MinStack {
// each entry stores (value, minimum so far)
stack: Vec<(i32, i32)>,
}
impl MinStack {
fn new() -> Self {
MinStack { stack: Vec::new() }
}
fn push(&mut self, val: i32) {
let current_min = match self.stack.last() {
Some(&(_, m)) => m.min(val),
None => val,
};
self.stack.push((val, current_min));
}
fn pop(&mut self) {
self.stack.pop();
}
fn top(&self) -> i32 {
self.stack.last().unwrap().0
}
fn get_min(&self) -> i32 {
self.stack.last().unwrap().1
}
}
fn check(got: i32, want: i32) {
println!("{} {} {}", if got == want { "PASS" } else { "FAIL" }, got, want);
}
fn main() {
let mut s = MinStack::new();
s.push(-2); s.push(0); s.push(-3);
check(s.get_min(), -3);
s.pop();
check(s.top(), 0);
check(s.get_min(), -2);
s.push(-2); s.push(-2);
s.pop();
check(s.get_min(), -2);
s.push(5);
check(s.top(), 5);
check(s.get_min(), -2);
}
Do all three Min Stack solutions pass the tests?
All three programs ran the same sequence of operations, including the classic example, pushing a duplicate minimum and popping one copy, and pushing a value larger than the minimum. Every check passed in Java, Python and Rust.
Also Read: Our data structures cheat sheet shows how stacks compare with other structures.
What are the 6 tips and tricks for an easy solution?
- Spot the pattern. When a question asks for an extra query in O(1) on a changing structure, think about saving the answer alongside each item as you insert it.
- Snapshot the state. The stack below an item is frozen while that item is on top, so a saved minimum can never go stale.
- Handle duplicates. In the two stack version, push to the min stack when the value is less than or equal to its top, otherwise popping one duplicate loses the minimum.
- Pick the right container. Use ArrayDeque in Java, a list in Python and a Vec in Rust. The old Java Stack class is synchronized and slower.
- Test the edges. Try repeated minimums, negative numbers, a single element and pushing after the stack was emptied.
- Say the trade off out loud. You spend O(n) extra memory to turn an O(n) query into O(1), and in an interview that reasoning matters more than the code.
What are the common mistakes people make?
These are the slips that break most first attempts at Min Stack:
- Keeping one min variable and never restoring it after the minimum is popped.
- Using strict less than in the two stack version, which breaks when the minimum appears twice.
- Comparing boxed Integer values with == in Java, which fails for numbers outside the small cache range.
- Recomputing the minimum on pop with a full scan, which sneaks O(n) back in.
- Forgetting that top and getMin need a non-empty stack and not saying so in the interview.
Where is this pattern used in the real world?
The Min Stack idea of saving an answer next to each item shows up in many places. Undo history in editors often stores a snapshot of state with each change, so stepping back restores everything at once.
Monitoring tools keep running minimums and maximums for metrics without rescanning old data. Database engines and caches also store precomputed answers next to the data to keep lookups fast.
Which earlier posts in the series should you read?
If Min Stack feels new, these earlier posts build the skills it leans on:
- Day 1, Two Sum for hash map basics.
- Day 2, Best Time to Buy and Sell Stock for tracking a running minimum, the same idea we used today.
- Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams for the counting toolkit.
- Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water for two pointers.
- Day 10, Longest Substring Without Repeating Characters, Day 11, Longest Repeating Character Replacement and Day 12, Minimum Window Substring for the sliding window section.
- Day 13, Valid Parentheses for your first stack problem.
Conclusion
Min Stack comes down to one idea: let every item remember the minimum at the time it was pushed. Then push, pop, top and getMin all run in O(1). Try rewriting it from memory, then run it through the checks above. Next up we keep going with stacks.
Frequently asked questions
What is the time complexity of Min Stack?
Push, pop, top and getMin all run in O(1) time. The extra space is O(n) because each item stores the minimum at the time it was pushed.
Why can’t I just keep one variable for the minimum in Min Stack?
When you pop the current minimum, a single variable cannot tell you the next smallest value without scanning the stack again. Storing the minimum with every item solves that.
Should I use one stack of pairs or two stacks for Min Stack?
Both run in O(1). One stack of pairs is simpler and harder to get wrong. Two stacks can use less memory when most pushed values are larger than the current minimum.
How do duplicate minimum values affect Min Stack?
In the pair approach they need no special care. In the two stack approach, push to the min stack when the value is less than or equal to its top so popping one duplicate keeps the other.
What problems are similar to Min Stack?
Max Stack, Min Queue, Sliding Window Maximum, Stock Span and Daily Temperatures all build on keeping extra information alongside a stack or deque.
