medium
Min Stack
Design a stack supporting push, pop, top and getMin, where getMin returns the smallest element currently in the stack. Every operation must run in constant time.
Constraints
- -2^31 ≤ val ≤ 2^31 - 1
- At most 3 · 10^4 operations
- pop, top, getMin are called only on a non-empty stack
Examples
in: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
out: -3, 0, -2
Recognition clues
- Stack semantics plus one extra aggregate
- The minimum only changes when the top changes
- Store the minimum *as of each push* alongside the value
Pattern
StackNesting and "last opened must be first closed" are LIFO by definition, so a stack tracks the currently open context. Any recursive process can also be flattened onto an explicit stack, which is how iterative DFS and expression parsers work.
Solution
Keep the main stack and a second stack of running minima. On push, push the value and push min(value, current min) on the min stack. On pop, pop both. getMin reads the top of the min stack. Since each level records the minimum of everything below it, popping restores the previous minimum automatically.
time O(1) per operationspace O(n)
Alternative approaches
- Store on the min stack only when the new value is ≤ the current minimum to save space. A single stack storing differences from the min works with careful arithmetic.
Code it yourself
Solve in
Hints: