Min Stack
Module 8 · Stacks
Problem
Design a stack supporting push, pop, top, and getMin — all in
O(1). getMin returns the minimum element currently in the stack.
Examples
Example 1
Input
push(-2), push(0), push(-3), getMin()Output-3Example 2
Input
pop(), top()Output0Example 3
Input
getMin()Output-2Explanation. minimum recovered after the pop
Constraints
≤ 3·10⁴ operations · pop/top/getMin always called on a non-empty stack.
Attempt it first
The trap is version one: keep a single min variable. It breaks — find
the exact operation where, before reading on (the example above walks
you right into it). Then ask: what information would you have needed to
keep?