Min Stack

Design a stack that supports push, pop, top, and getMin operations, all in O(1) time.

• push(val): Pushes element val onto stack.
• pop(): Removes element on top of stack.
• top(): Gets the top element.
• getMin(): Retrieves minimum element in the stack.

A standard stack gives O(1) push/pop, but finding the minimum usually takes O(N). To get O(1) min, we trade Space for Time.

Strategy:
Maintain a second stack, minStack. whenever we push a value x onto the mainStack, we also push min(x, minStack.top()) onto the minStack. The top of minStack always represents the minimum of the mainStack at that height.