155. Min Stack
Design a stack that can also report its smallest element at any moment — with every operation running in O(1) time.
Implement a MinStack class with four methods: push(val) adds val on top, pop() removes the top element, top() returns the top element without removing it, and get_min() (getMin in C++/Java) returns the smallest value currently in the stack.
Your class is driven by a scripted sequence of operations read from input; pop, top, and getMin are only ever issued while the stack is non-empty. Print the value returned by each top and getMin call, one per line, in the order the calls happen.
Example 1:
Input: ops = [push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()]
Output: [-3, 0, -2]
Explanation: After pushing -2, 0, -3 the minimum is -3. Popping the -3 exposes 0 on top, and the minimum falls back to -2.
Example 2:
Input: ops = [push(5), push(1), top(), getMin(), pop(), getMin()]
Output: [1, 1, 5]
Explanation: With 5 then 1 pushed, both top and getMin return 1. After popping the 1, only 5 remains, so getMin returns 5.
Constraints:
- 1 ≤ q ≤ 3 * 10⁴
- -10⁹ ≤ x ≤ 10⁹
- pop, top, and getMin are never called on an empty stack
Hints:
A plain dynamic array already gives you push, pop, and top in O(1) — the only hard part is answering getMin without scanning everything.
Store, next to each element, the minimum of everything at or below it in the stack. Then getMin is just a peek — and popping automatically restores the previous minimum, because each entry remembers the state of the world when it was pushed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Expected output: [-3, 0, -2]