Topic · StackMedium
Min Stack
Understand the problem
Design a stack that supports 4 operations, all in O(1): push(val), pop(), top() (peek at the top) and getMin() (get the smallest element currently in the stack).
ts
push(-2); push(0); push(-3)
getMin() // -3
pop()
top() // 0
getMin() // -2The challenge is getMin() in O(1): you cannot rescan everything on each query.
The trick is to remember the minimum at each level of the stack.
Basic approach
getMin O(n) per call, other operations O(1)ts
class MinStackNaive {
private stack: number[] = []
push(val: number) { this.stack.push(val) }
pop() { this.stack.pop() }
top() { return this.stack[this.stack.length - 1] }
getMin() {
// Scan the whole stack on every call
return Math.min(...this.stack)
}
}Why this approach is slow:
push/pop/top are fast, but getMin must walk through all elements each time → O(n).
The problem requires O(1), so this approach does not qualify.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.