DSA problem
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; void push(int val) pushes val onto the stack; void pop() removes the element on top; int top() returns the top element; and int getMin() returns the minimum element on the stack.
You must implement a solution with O(1) time complexity for each operation, including getMin. A naive implementation could store all values in a single stack and scan it on every getMin call — that is O(n) per call and easily fails the constant-time requirement.
The standard trick is to use two stacks: a "main" stack holding every pushed value, and an auxiliary "min" stack whose top always equals the minimum of the main stack at this moment. When you push val, push it onto the main stack as usual, and also push it onto the min stack if it is less than or equal to the current min (using less-than-or-equal handles duplicates correctly). When you pop, pop from the main stack, and also pop from the min stack if the popped value equals the current min.
That maintains the invariant that getMin is just minStack.top(). All four operations become straightforward O(1) work, and the total space is at worst 2n integers. This is the canonical "auxiliary structure tracks an aggregate of a primary structure" design pattern.
Examples
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]][null,null,null,null,-3,null,0,-2]["MinStack","push","push","getMin","push","getMin"]
[[],[5],[3],[],[3],[]][null,null,null,3,null,3]["MinStack","push","top","getMin"]
[[],[7],[],[]][null,null,7,7]Constraints
- -2^31 <= val <= 2^31 - 1
- Methods pop, top, and getMin operations will always be called on non-empty stacks.
- At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.