Min Stack
Implement a stack with push, pop, top, and min operations. min returns the smallest current value. Each operation must take constant time.
Work through the cases
3 examplesInput notation
One command per line: push x, pop, top, or min. Queries and pop occur only on a nonempty stack.Expected result
Print a value for each top or min command.Case 1
Input
push 5 push 2 min pop top
Expected output
2 5
Case 2
Input
push -3 push 7 min top
Expected output
-3 7
Case 3
Input
push 2 push 2 pop min
Expected output
2
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
getMin must be O(1) like push/pop. Scanning the stack is linear, and there are up to 3 × 10^4 calls. The minimum changes only when a smaller value is pushed or the current min is popped. A parallel min-stack stores \min(x, current min ) on each push and pops in lockstep.
class MinStack {
private Deque<Integer> stk1 = new ArrayDeque<>();
private Deque<Integer> stk2 = new ArrayDeque<>();
public MinStack() {
stk2.push(Integer.MAX_VALUE);
}
public void push(int val) {
stk1.push(val);
stk2.push(Math.min(val, stk2.peek()));
}
public void pop() {
stk1.pop();
stk2.pop();
}
public int top() {
return stk1.peek();
}
public int getMin() {
return stk2.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.