Min Stack
Part of Practice: Classic Stacks
Design a stack that, in addition to the usual operations, can report its smallest element instantly. Implement a class with four methods: push(val) adds a value on top, pop() removes the top, top() returns the top without removing it, and getMin() returns the minimum value currently in the stack.
The catch: every method must run in O(1) time — you cannot scan the stack to find the minimum. Calls to pop, top, and getMin are guaranteed to arrive only when the stack is non-empty.
Examples
- Input:
- push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
- Output:
- getMin() → -3, top() → 0, getMin() → -2
After pushing -2, 0, -3 the minimum is -3. Popping removes -3; the top is now 0, and the minimum falls back to -2 — the structure must remember that earlier minimum.
- Input:
- push(5), push(5), getMin(), pop(), getMin()
- Output:
- getMin() → 5, getMin() → 5
Duplicate minimums: after popping one 5, the other 5 is still there, so the minimum must remain 5. A design that stores the minimum only once breaks here.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.