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.

Visualize two stacks growing in parallel. The MinStack tracks the minimum value seen 'so far'.