Min Stack

Problem

Design a stack that, in addition to the usual push, pop, and top, can report the smallest element currently in the stack. Every operation, including getMin, must run in constant time.

Implement the class MinStack:

• MinStack() creates an empty stack.
• push(val) pushes val on top.
• pop() removes the top element.
• top() returns the top element without removing it.
• getMin() returns the minimum element currently in the stack.

Constraints:

• Every value fits in a signed 32-bit integer.
• pop, top, and getMin are never called on an empty stack.
• Up to 50,000 operations are issued in total.

Examples

• push(4), push(9), push(1), getMin() → 1. Then pop(), top() → 9, and getMin() → 4, because once 1 is gone the smallest remaining value is 4.
• push(-1), push(-1), push(3), getMin(), pop(), pop(), getMin() → -1, -1. Two copies of the minimum were pushed, so popping one copy must not lose the other.
• push(12), getMin() → 12. A single element is its own minimum.

Hints

1. Scanning the stack on every getMin is O(n). What could you record at push time so the answer is already known?
2. The minimum of the stack after a pop is exactly the minimum it had before the popped element was pushed. That history is itself stack-shaped.
3. Keep a second stack (or a tuple per entry) holding "minimum so far" alongside every element.