Problem overview
A stack gives values back in the opposite order they went in. The class MinStack has to behave like a stack, with push, pop and top, and it also has to answer getMin: the smallest value currently in the stack. Every operation must take constant time. The input is a list of operations applied to one new MinStack, and the output is what the top and getMin calls return. The stack is never empty when pop, top or getMin is called.
Take the first example: push -2, push 0, push -3. The stack holds -2, 0, -3 with -3 on top, so getMin() gives -3. After pop() removes -3, top() gives 0 and getMin() gives -2. The output is -3 0 -2. The point of that example is that when the minimum leaves the stack, the minimum from before it arrived comes back.
Approach: remember the minimum at every depth
The obvious way to find the smallest value is to look at all of them, which costs O(n) per getMin call. With up to 200,000 operations that is too slow, and the statement asks for O(1).
Keeping one variable with the current minimum is not enough: after the minimum is popped, the variable would have to be recomputed from what is left. The fix is to store more. A value can only leave the stack after every value above it has left, so the values below it do not change while it is in the stack. That means the minimum of "this value and everything below it" can be computed once, when the value is pushed, and written down next to it.
The class therefore keeps two vectors 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 describes the whole stack as it is now, so getMin only reads it. Popping removes the last entry of both, and the previous entry of minStack is the minimum the stack had before that value arrived.
After pushing -2, 0 and -3, the two vectors hold:
stack: -2 0 -3
minStack: -2 -2 -3The 0 does not lower the minimum, so its entry repeats -2. After the pop, the last entry of minStack is -2 again.
Step by step
- Declare
stackas avector<int>underpublic:. The end of a vector is the top of the stack, becausepush_back,backandpop_backall work at that end in constant time. - Declare
minStackas a secondvector<int>. Its entry at each depth is the smallest of the value at that depth and everything under it. - In
push, addvaltostackwithpush_back. - Start
currentMinatval. If the stack was empty,valis its only value and so its minimum. - If
minStackis not empty, lowercurrentMinwithmin(currentMin, minStack.back()). The last entry already is the smallest of everything below, so one comparison is enough. - Push
currentMinontominStack. Both vectors now have the same size. Equal values are pushed too, so a minimum that was pushed twice is remembered twice. - In
pop, remove the last element of both vectors. They must stay the same size. topreturnsstack.back(), which reads the last element and removes nothing.getMinreturnsminStack.back(), the answer that was stored when the top value arrived.
The solution in C++
class MinStack {
public:
vector<int> stack;
vector<int> minStack;
void push(int val) {
stack.push_back(val);
int currentMin = val;
if (!minStack.empty()) {
currentMin = min(currentMin, minStack.back());
}
minStack.push_back(currentMin);
}
void pop() {
stack.pop_back();
minStack.pop_back();
}
int top() {
return stack.back();
}
int getMin() {
return minStack.back();
}
};
The C++ details worth a closer look:
- Vectors as stacks. A
vectordoes everything a stack needs at its end, in amortized constant time. The standard library also hasstd::stack, but it has nobeginor indexing, and a plain vector is simple enough here. back()andpop_back()on an empty vector are undefined behaviour. The constraints promise thatpop,topandgetMinare only called on a non-empty stack, so the code does not check.pushdoes checkminStack.empty(), because it is the one call made on an empty stack.pop_back()returns nothing. It removes the element but does not hand it back, which is whypopin this class returnsvoid.- Full 32-bit range. Values go from -2147483648 to 2147483647, and
intholds exactly that. The code only compares values and never adds or subtracts them, so no overflow can happen. Withpush(INT_MIN)thenpush(INT_MAX),getMin()returns -2147483648 andtop()returns 2147483647.
Complexity
Time: O(1) per operation. Every method does a fixed number of vector operations at the end of a vector. push_back is amortized constant: now and then the vector reallocates and copies its elements, but that cost is spread over many pushes.
Space: O(n). For n values in the stack, the two vectors hold 2n integers. That is the price of constant-time getMin.
Edge cases and common mistakes
- Duplicate minimums. Push 4, 2, 2, then pop once:
getMin()returns 2, because the other 2 is still there. After a second pop it returns 4. A design that stores each distinct minimum only once breaks here. Storing a minimum per depth, as this one does, handles it for free. - One variable for the minimum. It is correct until the minimum is popped, and then there is no way to recover the previous one in constant time.
- Different top and minimum. After pushing 3, 1, 2,
top()is 2 andgetMin()is 1. Returning one when the other is asked for is an easy slip when the two vectors are named alike. - Popping only one vector. If
popforgetsminStack.pop_back(), the sizes drift apart andgetMinkeeps answering for values that have left. - Comparing with the wrong entry. The comparison uses
minStack.back(), the minimum of everything below. Comparing withstack.back()would only look at the value just under the new one.
Testing
- push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() prints
-3 0 -2. - push(5), push(5), push(7), getMin(), pop(), pop(), getMin(), top() prints
5 5 5. - push(3), top(), getMin(), push(1), push(2), top(), getMin(), pop(), pop(), getMin() prints
3 3 2 1 3. - push(4), push(2), push(2), pop(), getMin(), pop(), getMin() prints
2 4.
