Problem overview
A stack gives values back in the opposite order they arrived. The class MinStack must behave like one, with two requirements: push(val) puts a number on top, pop() removes the top value, top() returns the top value without removing it, and getMin() returns the smallest value currently in the stack. Every operation has to run in constant time. pop, top and getMin are only called on a stack that isn't empty.
Take the first example: push -2, 0 and -3, then call getMin(). The stack holds -2, 0 and -3, so the answer is -3. After pop() removes -3, top() returns 0 and getMin() returns -2. The output for the whole run is -3 0 -2.
Approach: remember the minimum at every depth
The obvious getMin scans the whole array, which costs O(n) per call. A single variable holding the smallest value seems to fix that, but it breaks on pop. After pushing -2, 0 and -3 the variable holds -3. Once -3 is popped, the variable should go back to -2, and nothing in the variable remembers that. With a single variable that keeps the smallest value pushed so far, getMin() still returns -3 after the pop.
The fix rests on one observation: a value leaves the stack only after every value above it has left. So the values below it don't change while it is there, and the minimum of everything from the bottom up to that value can be computed once, when the value is pushed. Store it next to the value. A second array, minStack, does this: its entry at each depth is the smallest value at that depth and below. The top entry then describes the whole stack as it is now, and popping removes the top entry of both arrays together.
Here is the state while the first example runs, with the top at the right:
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]
After the pop, the top of minStack is -2 again, with no searching.
Step by step
- Declare
stackas anumber[]field, empty. Arraypushandpopboth work at the end, so the end of the array is the top of the stack. - Declare
minStackthe same way. It always has the same length asstack. - In
push, putvalonthis.stackfirst, as any stack would. - Start
currentMinatval. If the stack was empty,valis its only value and so its smallest. It is aletbecause the next step may lower it. - Compare with the minimum below. If
minStackisn't empty, its top entry is already the smallest of everything underval, so oneMath.minagainst it is enough. - Push
currentMinontominStack. Equal values are pushed too, so a minimum that was pushed twice is remembered twice. - In
pop, pop both arrays. Removing the top ofminStackuncovers the minimum the stack had before that value arrived. - In
top, return the last element ofstack, at indexthis.stack.length - 1. Reading it removes nothing. - In
getMin, return the last element ofminStack.
The solution in TypeScript
class MinStack {
stack: number[] = [];
minStack: number[] = [];
push(val: number): void {
this.stack.push(val);
let currentMin: number = val;
if (this.minStack.length > 0) {
currentMin = Math.min(currentMin, this.minStack[this.minStack.length - 1]);
}
this.minStack.push(currentMin);
}
pop(): void {
this.stack.pop();
this.minStack.pop();
}
top(): number {
return this.stack[this.stack.length - 1];
}
getMin(): number {
return this.minStack[this.minStack.length - 1];
}
}
A few TypeScript details:
- Field initialisers.
stack: number[] = [];declares the field and gives each newMinStackits own empty array, so two stacks never share their contents. - Types are only annotations. The
: numberand: voidare erased when the code is compiled to JavaScript. They check the calls at compile time and do nothing at run time. - Empty arrays.
pop()on an empty array returnsundefinedand readingstack[-1]also givesundefined, with no error. The constraints promise the stack isn't empty, so the lesson never relies on this. - Values near the limits. A
numberis a double, which holds every 32-bit integer exactly, so there is no overflow to worry about. Pushing 2147483647 and then -2147483648 gives -2147483648 fromgetMin().
Complexity
Time: O(1) per operation. Each method does a constant number of array reads, pushes and pops at the end of an array, plus one Math.min. The cost doesn't depend on how many values the stack holds.
Space: O(n) for n values on the stack. Every value has one entry in each array, so the memory is twice that of a plain stack, which is still linear.
Edge cases and common mistakes
- Keeping one running minimum. It can't go back up after a pop, as the example shows. That is why the minimum is stored per depth.
- Top and minimum differ. After pushing 3, 1 and 2,
top()is 2 whilegetMin()is 1. Returning the same value from both is a mistake. - Duplicates. After pushing 5, 5, 7 and popping twice, the stack still holds a 5, so
getMin()still returns 5. Because every push writes an entry intominStack, even when the new value equals the current minimum, each copy leaves with its own entry. - Forgetting one
pop. If onlystackis popped, the arrays get out of step andgetMindescribes values that are gone. - The first push. When
minStackis empty, reading its last element givesundefined, andMath.min(val, undefined)isNaN. Thelength > 0check avoids this.
Testing
- push -2, push 0, push -3, getMin, pop, top, getMin gives
-3 0 -2. - push 5, push 5, push 7, getMin, pop, pop, getMin, top gives
5 5 5. - push 3, top, getMin, push 1, push 2, top, getMin, pop, pop, getMin gives
3 3 2 1 3.
