Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
push(val) — pushes the element val onto the stackpop() — removes the element on the toptop() — gets the top elementgetMin() — retrieves the minimum element in the stackExample 1
Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: -3, 0, -2
-2^31 <= val <= 2^31 - 1All operations are valid.A second, parallel stack tracking the current minimum at each depth is the standard approach — push a new min value (or the same one) alongside every regular push.
The two stacks must always stay in sync — every push/pop on the main stack needs a matching push/pop on the min-stack, even when the value being pushed isn't a new minimum.
A more space-efficient (but trickier) alternative stores only the DIFFERENCE between each value and the min at push time, reconstructing the previous min from that delta on pop.
class MinStack {
private Deque<Integer> stack = new ArrayDeque<>();
private Deque<Integer> minStack = new ArrayDeque<>();
public void push(int val) {
stack.push(val);
// Push the new minimum — smaller of val or current min
int newMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
minStack.push(newMin);
}
public void pop() {
stack.pop();
minStack.pop(); // both stacks stay in sync
}
public int top() { return stack.peek(); }
public int getMin() { return minStack.peek(); }
}Time: O(1) all operations · Space: O(n)