Problem overview
A stack gives values back in reverse order: the last value pushed is the first popped. In JavaScript an array already behaves like one, because push and pop both work at its end. The lesson asks for a class, MinStack, with four methods: push(val), pop(), top() and getMin(). The last one must return the smallest value currently in the stack, and every method has to run in constant time.
Take the first example: push -2, push 0, push -3. The stack holds -2, 0 and -3, with -3 on top, so getMin() returns -3. After pop() the stack holds -2 and 0. Now top() returns 0 and getMin() returns -2: the minimum that was there before -3 arrived has come back.
The constraints say pop, top and getMin are only called on a non-empty stack, so the code needs no empty-stack checks.
Approach: remember the minimum at every depth
The obvious getMin scans the whole stack, which costs O(n) per call. Keeping a single variable with the smallest value fails as soon as that value is popped: the variable would have to be recomputed from what remains.
The fix comes from one observation. A value leaves the stack only after every value above it has left, so the values below it never change while it is in the stack. The minimum of "this value and everything below it" can therefore be computed once, when the value is pushed, and stored next to it.
So the class keeps two arrays of the same length. stack holds the values. minStack holds, at each depth, the smallest value from the bottom up to that depth. The last entry of minStack always describes the whole stack as it is now, so getMin only reads it. Popping removes the last entry of both arrays, which uncovers the previous minimum automatically.
Here are the two arrays during the first example:
push -2: stack [-2] minStack [-2]
push 0: stack [-2,0] minStack [-2,-2]
push -3: stack [-2,0,-3] minStack [-2,-2,-3]
pop: stack [-2,0] minStack [-2,-2]
Pushing 0 repeats the minimum -2 in minStack, because -2 is still the smallest value at that depth. After the pop, the last entry of minStack is -2 again, which is what getMin() returns.
Step by step
- Create
this.stackin the constructor as an empty array. The end of the array is the top of the stack. - Create
this.minStackas another empty array. Its entry at each depth is the smallest value of that depth and all the depths below it. - In
push, pushvalontothis.stackfirst, as on any stack. - Start a candidate minimum,
currentMin, equal toval. It is declared withletbecause the next step may lower it. If the stack was empty,valis the only value, so it is the minimum. - Compare with the old minimum. If
minStackis not empty, its last entry is already the smallest of everything belowval, so oneMath.minagainst that entry is enough. - Push
currentMinontominStack. Both arrays now have the same length. Equal values are pushed too, so a minimum that was pushed twice is remembered twice. - In
pop, pop from both arrays, one line each. They must stay the same size. - In
top, return the last element ofthis.stack, at indexlength - 1. Reading it removes nothing. - In
getMin, return the last element ofthis.minStack.
The solution in JavaScript
class MinStack {
constructor() {
this.stack = [];
this.minStack = [];
}
push(val) {
this.stack.push(val);
let currentMin = val;
if (this.minStack.length > 0) {
currentMin = Math.min(currentMin, this.minStack[this.minStack.length - 1]);
}
this.minStack.push(currentMin);
}
pop() {
this.stack.pop();
this.minStack.pop();
}
top() {
return this.stack[this.stack.length - 1];
}
getMin() {
return this.minStack[this.minStack.length - 1];
}
}
A few JavaScript details are worth knowing:
- State lives on
this. Eachnew MinStack()runs the constructor, so every instance gets its own two arrays. Withoutthis., a name likestackwould be a plain local variable that disappears when the constructor ends. - Array
pushandpopare amortized constant time. Both work at the end of the array. Usingshiftorunshiftat the front would be a trap, because they move every element. Math.mintakes numbers. Values from-2147483648to2147483647are far inside the range where JavaScript numbers are exact integers, so no overflow can happen here.- Methods that return nothing.
pushandpophave noreturn, so a call evaluates toundefined. OnlytopandgetMinproduce values. - The last element.
arr[arr.length - 1]reads it. A negative index likearr[-1]does not count from the end in JavaScript: it looks for a property named"-1"and givesundefined. (arr.at(-1)does count from the end.)
Complexity
Time: O(1) per operation. Each method does a fixed number of array reads, writes, one comparison, and at most one push or pop on each array.
Space: O(n). For n values on the stack, there are n entries in stack and n in minStack, so twice as many numbers as a plain stack, still linear.
Edge cases and common mistakes
- Duplicates of the minimum. Pushing 5, 5, 7 gives
minStack[5, 5, 5]. After two pops the stack holds one 5 andgetMin()still returns 5. A version that stores a new minimum only when it is strictly smaller would lose the second 5 and answer wrongly here. - A single value. After
push(3), bothtop()andgetMin()return 3. Theifinpushis skipped, andcurrentMinstays equal toval. - Top and minimum differ. After pushing 3, 1, 2,
top()returns 2 andgetMin()returns 1. After two pops, only 3 is left and it is the minimum again. - Popping only one array. The two arrays would drift out of step, and
getMinwould describe the wrong depth. - Using a single minimum variable. It breaks as soon as the minimum is popped, because nothing remembers the previous one.
- Scanning in
getMin. UsingMath.min(...this.stack)is correct but costsO(n)per call. With up to 200,000 calls, that is too slow, and a very long stack can also exceed the limit on how many arguments a spread call may pass.
Testing
- Push -2, 0, -3, then
getMin(),pop(),top(),getMin()gives-3 0 -2. - Push 5, 5, 7, then
getMin(),pop(),pop(),getMin(),top()gives5 5 5. - Push 3, then
top()andgetMin(), push 1 and 2, thentop(),getMin(),pop(),pop(),getMin()gives3 3 2 1 3. - Push -2147483648 then 2147483647:
getMin()gives-2147483648andtop()gives2147483647.
