Coding Interview PatternsMin Stack
MediumStacks
Min Stack
Explanation & Solution
Description
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 elementvalonto 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.
Examples
Example 1:
Input:
`
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
`
Output:[null,null,null,null,-3,null,0,-2]
0
null
1
null
2
null
3
null
4
-3
5
null
6
0
7
-2
Explanation:
`
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
`
Constraints
-2^31 <= val <= 2^31 - 1- Methods
pop,topandgetMinoperations will always be called on non-empty stacks - At most
3 * 10^4calls will be made topush,pop,top, andgetMin
Approach
Stacks pattern
1. Two Stacks Approach
- Maintain two stacks: a main stack for values and a min stack that tracks the minimum at each level
2. Push Operation
- Push the value onto the main stack
- Push
min(val, current minimum)onto the min stack - This ensures the min stack always has the current minimum at its top
3. Pop Operation
- Pop from both stacks simultaneously
- The min stack stays synchronized with the main stack
4. Top and GetMin
top()returns the top of the main stackgetMin()returns the top of the min stack- Both are O(1) operations
Key Insight
- By maintaining a parallel min stack, we trade O(n) extra space for O(1) getMin time
- Each position in the min stack stores the minimum of all elements from that position down to the bottom of the stack