Min Stack
A budgeting app keeps the history of an account balance on a stack. Each transaction pushes the new balance on top, and undo pops the most recent one. The app also warns users about the lowest balance in the current history, and that lookup has to be as cheap as every other operation.
Implement the MinStack class so that every method runs in O(1) time:
MinStack()starts with an empty history.push(val)pushes the balancevalon top.pop()removes the most recent balance (the undo).top()returns the most recent balance without removing it.getMin()returns the smallest balance currently in the history.
Balances are integers and can be negative (an overdraft). The tests call the methods one after another and never call pop, top or getMin on an empty history.
Input: ["MinStack","push","push","push","push","getMin","pop","getMin","pop","top","pop","getMin"] [[],[50],[20],[70],[10],[],[],[],[],[],[],[]] Output: [null,null,null,null,null,10,null,20,null,20,null,50]
Explanation: The lowest balance is 10 until that transaction is undone, then 20. Once 70 and 20 are undone as well, only 50 remains.
Input: ["MinStack","push","push","push","getMin","pop","pop","getMin","top"] [[],[-5],[-5],[3],[],[],[],[],[]] Output: [null,null,null,null,-5,null,null,-5,-5]
Explanation: The overdraft of -5 was pushed twice. Undoing 3 and one copy of -5 still leaves -5 as both the top and the minimum.
Constraints
- Every pushed value fits in a 32-bit signed integer.
- A single test makes no more than 30,000 method calls.
pop,topandgetMinare only called while the history is non-empty.
💡 Hint 1
The minimum can change when you pop. Can you remember what the minimum was at every depth of the stack?
💡 Hint 2
Store pairs (value, minimum so far), or keep a second stack of minimums.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Keep a single stack of pairs: each entry stores the value and the minimum of the stack at the moment it was pushed (min(val, previousMin)). top reads the value, getMin reads the stored minimum, and popping automatically restores the previous minimum.
class MinStack {
constructor() {
this.stack = [];
}
push(val) {
const min = this.stack.length ? Math.min(val, this.getMin()) : val;
this.stack.push([val, min]);
}
pop() {
this.stack.pop();
}
top() {
return this.stack[this.stack.length - 1][0];
}
getMin() {
return this.stack[this.stack.length - 1][1];
}
}class MinStack {
private final Deque<int[]> stack = new ArrayDeque<>();
public MinStack() {}
public void push(int val) {
int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
stack.push(new int[] { val, min });
}
public void pop() { stack.pop(); }
public int top() { return stack.peek()[0]; }
public int getMin() { return stack.peek()[1]; }
}No submissions yet. Press Submit to run your code against every test.
class MinStack {
constructor() {
}
/** @param {number} val */
push(val) {
}
pop() {
}
/** @return {number} */
top() {
}
/** @return {number} */
getMin() {
}
}Run your code to see results here.