Problem
Design a stack that supports the standard stack operationspush, pop, and top, along with a getMin operation that returns the minimum element currently present in the stack.
All operations should run in O(1) time.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
push(-2)
push(0)
push(-3)
getMin()
pop()
top()
getMin()Output
-3
0
-2Example 2
Input
push(2)
push(0)
push(3)
push(0)
getMin()
pop()
getMin()
pop()
getMin()Output
0
0
0Solution
This solution uses the Stack pattern. We maintain two stacks: one stack stores the actual values, while the second stack stores the minimum value at each level of the stack.Whenever a value is pushed, we also push the smaller value between the new value and the current minimum onto the minimum stack. Therefore, the top of the minimum stack always represents the minimum value in the entire stack.
When an element is removed, we remove the top element from both stacks. This keeps the two stacks synchronized and allows
getMin() to return the minimum in O(1) time.
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(val, minStack.peek()));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}Complexity
All operations perform a constant number of stack operations, sopush, pop, top, and getMin each have O(1) time complexity.
The two stacks store up to n elements, so the extra space complexity is
O(n).