301. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• push(val) pushes the element val onto the stack.
• pop() removes the element on the top of the stack.
• top() gets the top element of the stack.
• getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

The challenge is supporting O(1) getMin(). A naive approach would scan the entire stack for the minimum. The trick is maintaining a parallel stack that tracks the minimum at each level.

Requirements

1. All Operations O(1)

• push, pop, top: standard stack operations
• getMin: return current minimum in O(1)

Example Usage

const stack = new MinStack();
stack.push(-2);
stack.push(0);
stack.push(-3);
stack.getMin(); // -3
stack.pop();
stack.top();    // 0
stack.getMin(); // -2

Real-World Context

• Monitoring systems: Tracking minimum latency in a sliding window
• Trading platforms: Maintaining minimum price while processing orders
• Undo systems: Tracking the minimum state across operation history