Coding · Stacks
Min Stack
- Reported once
- Medium
- SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Design a stack that supports push, pop, top and getMin, where getMin returns the smallest value currently in the stack, and every operation runs in constant time. For example, after pushing -2, 0 and -3, getMin returns -3; after one pop, top returns 0 and getMin returns -2. Pop, top and getMin are only ever called on a non-empty stack, and there can be tens of thousands of operations.
Restated in our own words, not a quote from Swiggy or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: do all four operations really need constant time, or only getMin? Is pop, top or getMin ever called on an empty stack, and if so what should they return? Are values plain integers, and may they repeat? Is extra memory proportional to the stack size acceptable?
I will assume constant time for all four, no calls on an empty stack, integer values with repeats allowed, and O(n) extra space is fine. I will mention that array push and pop in JavaScript are amortized O(1), since the underlying storage occasionally grows.
Brute force
Say the obvious answer and why it is too slow.
The obvious design is a plain array. Push, pop and top are O(1), and getMin scans the whole array to find the smallest value.
That makes getMin O(n). With a stack of 30,000 values and 30,000 getMin calls, that is nearly a billion comparisons, and the point of the question is that getMin should not depend on the size at all. Keeping the elements in a sorted structure gives O(log n) for every push and pop, still not constant. Neither approach meets the requirement, so we need to store a little extra information with the stack itself.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n) per getMin
- Time
- O(1) per operation
- Space
- O(n)
The key observation: while an element sits in the stack, everything below it stays exactly the same. So the minimum of "this element and everything below it" never changes while the element is there. I can compute it once, at push time, and store it next to the value.
Each stack entry is a pair [value, minSoFar]. On push, the new minSoFar is the smaller of the new value and the minSoFar of the current top (or just the value if the stack is empty). On pop, I discard the top pair, and the pair underneath still holds the minimum for the smaller stack, so the old minimum is restored with no extra work. Top reads the value of the last pair and getMin reads its minSoFar. All four are O(1).
The invariant is: for every entry, minSoFar equals the smallest value among that entry and all entries below it. It holds after a push by the rule above and trivially after a pop, since the entries below are untouched.
There is a well-known variant with a second stack of minima that only pushes when the new value is less than or equal to the current minimum. It works, but the equal case is easy to get wrong when values repeat, which is why I prefer pairs. The pattern is augmenting a stack with a running aggregate, and the same trick works for maximum, sum or gcd.
Walk it through
A dry run on the example, step by step.
| step | call | stack | returns |
|---|---|---|---|
| 1 | push(-2) | (-2,-2) | null |
| 2 | push(0) | (-2,-2) (0,-2) | null |
| 3 | push(-3) | (-2,-2) (0,-2) (-3,-3) | null |
| 4 | getMin() | (-2,-2) (0,-2) (-3,-3) | -3 |
| 5 | pop() | (-2,-2) (0,-2) | null |
| 6 | top() | (-2,-2) (0,-2) | 0 |
| 7 | getMin() | (-2,-2) (0,-2) | -2 |
The example pushes -2, 0, -3, then asks getMin, pops, asks top and asks getMin.
Push -2: stack is empty, so the pair is (-2, -2). Push 0: the current top minimum is -2, so the pair is (0, -2). Push -3: the pair is (-3, -3). getMin reads the top pair and returns -3. Pop removes (-3, -3), leaving (-2, -2) and (0, -2). Top returns 0, and getMin returns -2, restored with no recomputation.
The trace table shows the pairs from bottom to top after each call. The result list for the whole sequence is [null, null, null, null, -3, null, 0, -2], with the constructor and the push and pop calls returning null.
The code
Runnable JavaScript, checked against test cases.
class MinStack {
constructor() {
this.entries = [];
}
push(value) {
const smallest =
this.entries.length === 0 ? value : Math.min(value, this.getMin());
this.entries.push([value, smallest]);
}
pop() {
this.entries.pop();
}
top() {
return this.entries[this.entries.length - 1][0];
}
getMin() {
return this.entries[this.entries.length - 1][1];
}
}
function run(ops, args) {
let stack = null;
const results = [];
for (let i = 0; i < ops.length; i++) {
if (ops[i] === "MinStack") {
stack = new MinStack();
results.push(null);
} else {
const result = stack[ops[i]](...args[i]);
results.push(result === undefined ? null : result);
}
}
return results;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
A single element: its pair is (value, value), so top and getMin agree. Duplicates of the minimum, for example pushing 1 twice and popping once, are safe because each pair carries its own minimum, so the surviving 1 still reports 1. Pushing a larger value never changes the reported minimum, because the new pair copies the one below it.
Ascending pushes keep the minimum at the first value for the whole run; descending pushes update it every time. After popping everything and pushing again, the first push sees an empty stack and starts a fresh minimum. Calls on an empty stack are outside the stated contract, so the code does not guard them, and I would say so out loud.
Follow-ups to expect
Where the interviewer pushes next.
- How would you cut the extra space by storing the minimum only when it changes?
- How would you add getMax in the same constant time?
- How would you build the same structure with a queue instead of a stack?
- What would you change to make the stack safe for several threads?
Where candidates slip
The mistakes this problem punishes.
The classic bug is the two-stack version that pushes onto the minimum stack only when the new value is strictly smaller than the current minimum. With duplicates, popping one copy of the minimum removes it from the minimum stack while another copy is still in the main stack, and getMin is then wrong. The fix is to push on less-than-or-equal, or to use pairs as above.
Other slips: keeping one running minimum variable, which cannot be restored after a pop; recomputing the minimum with a scan on every getMin; forgetting to compare against the top's minimum on push and storing only the new value; and returning the pair instead of just the value from top.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.