Repository navigation
052 — Min Stack
LeetCode 155 · Medium. Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time.
Picture that same stack of cafeteria trays, but now imagine a helper standing next to it whose only job is to whisper "the lightest tray currently in the stack is this one" every time you ask — instantly, without looking through the pile. The naive way to answer "what's the lightest tray right now?" is to lift every tray off, check, and put them all back — slow, and it defeats the purpose of a stack. The clever trick: have the helper keep their own private stack, one entry per tray, where each entry remembers "the minimum among everything at or below this height, at the moment this tray was placed." When a tray is removed, the helper just pops their own note too — no recomputation needed, because the note for the new top was already correct the moment it was written.
"Design a stack that also supports getMin()/getMax() in O(1)" is the tell: whenever an aggregate (min, max) needs to be queryable in constant time on a structure that only ever changes at one end, the fix is to shadow it with a second stack that caches the running aggregate at each push — not to recompute the aggregate from the live data on demand. This is a plain-stack design problem, not a monotonic-stack one (there's no discarding of dominated elements — every pushed value gets its own permanent slot in both stacks), but it leans on the exact same LIFO "undo is free" property that makes monotonic stacks work.
A single underlying array works for push, pop, and top in O(1), but if getMin() isn't cached, it has to scan everything currently in the stack every time it's asked.
class MinStackBruteForce {
private var stack: [Int] = []
func push(_ val: Int) {
stack.append(val)
}
func pop() {
stack.removeLast()
}
func top() -> Int {
stack.last!
}
func getMin() -> Int {
stack.min()! // O(n) scan every single call
}
}Big-O: push/pop/top are O(1). getMin() is O(n) — it re-derives the minimum from scratch by scanning the whole stack every time it's called. O(n) space for the stack.
Maintain a second, parallel stack — minStack — where minStack[i] is the minimum of everything in the main stack from the bottom through index i. Every push records "the min so far including me"; every pop discards both stacks' top entries together, so the new top of minStack is always correct without recomputing anything.
class MinStack {
private var stack: [Int] = []
private var minStack: [Int] = []
func push(_ val: Int) {
stack.append(val)
let newMin = minStack.last.map { Swift.min($0, val) } ?? val
minStack.append(newMin)
}
func pop() {
stack.removeLast()
minStack.removeLast()
}
func top() -> Int {
stack.last!
}
func getMin() -> Int {
minStack.last!
}
}
// smoke test
let minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
print(minStack.getMin()) // -3
minStack.pop()
print(minStack.top()) // 0
print(minStack.getMin()) // -2Big-O: Every operation — push, pop, top, getMin — is O(1). O(n) space, doubled versus a plain stack (one entry in minStack per entry in stack).
The brute force treats getMin() as a question to be answered fresh every time, which means paying O(n) on every single call even though most of the stack didn't change since the last call. The optimal solution instead treats "what's the min so far" as a piece of state that only ever needs updating exactly once per push — the instant a value is pushed, its "min including me" is fully determined and never changes again until it's popped. Caching that answer at push time, one slot per element, converts getMin() from a repeated O(n) re-derivation into a single O(1) lookup, at the cost of doubling the space.
-
Stacks — both the primary data stack and the auxiliary min-tracking stack are plain LIFO structures built directly on
Array.append/popLast. - Monotonic Stack — not a genuine match (nothing is discarded early; every pushed value keeps its own slot), but it's the closest pattern-family chapter here, and the same "each stack level caches something so it never needs recomputing" instinct is a cousin of the domination argument that chapter formalizes.
-
Big-O Notation — for the
O(n)→O(1)trade-off reasoning above.
Min Stack is a stack with a helper standing beside it, jotting down "the lightest tray so far" on a sticky note every time a new tray is placed — so the current minimum is always one glance away, never a full re-count.
Suppose you push 5, then 3, then 3 again, then pop once. Walk through what minStack holds after each operation, and explain why storing a new min-so-far entry for the second 3 (rather than skipping it as "unchanged") is necessary for pop() to keep working correctly.
⬅️ Previous: Valid Parentheses · Next: Evaluate Reverse Polish Notation ➡️