Min Stack —
Minimum in O(1). Always.
Design a stack that supports push, pop, and getMin — all in O(1) time. The trick is a second auxiliary stack that tracks the current minimum at every state. When elements pop off the main stack, the min stack pops in sync — so the minimum is always correct. Watch both stacks update together on LearnBug and the design becomes immediately obvious.
What is the problem?
Design a data structure that supports: push(val) — add to top, pop() — remove from top, top() — peek at top, and getMin() — retrieve the minimum element — all in O(1) time. The challenge: when you pop the current minimum, what's the new minimum? You can't scan the whole stack — that's O(n). The auxiliary min stack solves this.
Why two stacks solve it
The auxiliary stack tracks the minimum at every level. When you push a value, push min(val, current_min) onto the min stack too. When you pop, pop both stacks together. The top of the min stack is always the current minimum — no scanning needed. On LearnBug both stacks are visible side by side, and you watch them stay perfectly in sync.
Push 5, 3, 7, 2 — then pop — track min throughout
push(5) — both stacks start
Main stack: [5]. Min so far = 5. Min stack: [5].
Main Stack
Min Stack
getMin() = 5
push(3) — new minimum
Push 3 to main. Min(3, 5) = 3. Push 3 to min stack.
Main Stack
Min Stack
getMin() = 3
push(7) — not a new minimum
Push 7 to main. Min(7, 3) = 3. Push 3 again to min stack — keeps current min recorded.
Main Stack
Min Stack
getMin() = 3 (unchanged)
push(2) — new minimum
Push 2 to main. Min(2, 3) = 2. Push 2 to min stack.
Main Stack
Min Stack
getMin() = 2
pop() — remove 2. Min restores to 3!
Pop main stack (removes 2). Pop min stack (removes 2). New top of min stack is 3 — minimum is automatically restored.
Main Stack
Min Stack
getMin() = 3 ✓ restored automatically
Min Stack implementation
class MinStack:
def __init__(self):
self.stack = [] # main stack
self.min_stack = [] # tracks current min at every level
def push(self, val):
self.stack.append(val)
# push min of new val vs current min
current_min = min(val, self.min_stack[-1]) if self.min_stack else val
self.min_stack.append(current_min)
def pop(self):
self.stack.pop()
self.min_stack.pop() # always pop both in sync
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1] # O(1) — always at topTime & Space Complexity
Frequently asked questions
Why can't I just track the minimum in a single variable?
A single variable works for push — update if new value is smaller. But on pop, if you remove the current minimum, you don't know what the previous minimum was without scanning the entire stack in O(n). The min stack solves this by recording the minimum at every level, so popping always reveals the correct previous minimum.
Can I save space by only pushing to min stack when a new minimum is found?
Yes — push to the min stack only when val <= min_stack[-1], and pop from the min stack only when main_stack[-1] == min_stack[-1]. This saves space when there are many non-minimum pushes, but complicates the logic slightly. The two-parallel-stacks approach is simpler and more commonly expected in interviews.
Can I design a Max Stack similarly?
Exactly the same approach — just push max(val, max_stack[-1]) to the auxiliary stack instead of min. getMax() returns max_stack[-1] in O(1). The pattern — auxiliary stack tracking aggregate across push/pop — is reusable for any historical aggregate.
What is the LeetCode problem for this?
LeetCode 155 — Min Stack. One of the most classic stack design problems in interviews. It's often the first "design a data structure" question candidates encounter, and it teaches the key insight: use additional space to achieve better time complexity.
How does this relate to monotonic stacks?
Both use auxiliary stack behaviour to avoid O(n) scanning. The min stack maintains the historical minimum across arbitrary push/pop operations. A monotonic stack maintains a sorted sequence to solve range-based problems like next greater element. They share the principle: carefully maintain stack invariants to enable O(1) answers to queries that would otherwise require O(n) scans.
Watch both stacks stay in sync on your own operations
Paste your Min Stack operations into LearnBug and see the main and min stacks update together at every step.