Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time. Implement MinStack() and: - push(val): Push val onto the stack. - pop(): Remove the top element. - top(): Return the top element. - getMin(): Retrieve the minimum element. DE Shaw Tier 2 — LC 155. Optimal: Two stacks — main stack and minStack. On push, also push to minStack if val <= minStack.top(). On pop, also pop from minStack if top equals popped value. Alternative: Store (val, currentMin) pairs in one stack.