Q7: How do you design a Min Stack that retrieves the minimum element in O(1) time?
Maintain an auxiliary stack (minStack) alongside the primary stack. When pushing value x, push Math.min(x, minStack.peek()) onto minStack. When popping from the primary stack, pop from minStack simultaneously.
Min Stack Implementation
import java.util.ArrayDeque;
import java.util.Deque;
public class MinStack {
private final Deque<Integer> stack = new ArrayDeque<>();
private final Deque<Integer> minStack = new ArrayDeque<>();
public void push(int val) {
stack.push(val);
int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
minStack.push(currentMin);
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}💡 Keeps stack min state in sync across every push and pop operation.
Key Takeaways
- Auxiliary minStack tracks the current minimum value at every stack depth.
- All operations (
push,pop,top,getMin) run in $O(1)$ time.
Knowledge Check
What is the auxiliary space complexity of the Min Stack implementation?