Problem overview
A stack gives values back in reverse order: the last value pushed is the first one popped. The MinStack class must behave like a stack and also answer one more question at any moment: what is the smallest value it holds right now? Every operation, Push, Pop, Top and GetMin, has to run in constant time. The tests only call Pop, Top and GetMin on a non-empty stack, and values can be any int.
Take the first example. After pushing -2, 0 and -3, the stack holds those three values with -3 on top, so GetMin returns -3. After Pop removes -3, Top returns 0 and GetMin returns -2. The minimum that was current before -3 arrived comes back. Running the lesson's class on this sequence prints -3, 0, -2.
Approach: remember the minimum next to every value
The obvious GetMin loops over everything in the stack and costs O(n) per call. Keeping a single variable min looks cheaper, but it breaks as soon as the minimum is popped: you would have to scan the rest of the stack to find the new one.
The way out is to notice that a value only leaves the stack after every value above it has left. So the values below it never change while it is in the stack, and the smallest value from the bottom up to that position can be computed once, when the value is pushed, and then kept. The class stores two stacks of equal height:
stackholds the values themselves.minStackholds, at each depth, the smallest value from the bottom of the stack up to that depth.
The top of minStack therefore describes the whole stack as it is now. Popping removes the top of both stacks, and the previous minimum is uncovered automatically. No search is needed.
Duplicates need no special case. In the second example, 5 is pushed twice and then 7. The two stacks hold 5, 5, 7 and 5, 5, 5. After two pops, one 5 remains in both, and GetMin still returns 5. The last line of that run prints 5 for GetMin and 5 for Top.
Step by step
- Declare
stackas a field of typeStack<int>with an initializer, so the object starts with an empty stack and needs no constructor. - Declare
minStackthe same way. Its entry at each depth is the minimum of the value at that depth and everything below. - In
Push, pushvalontostackfirst. The ordinary stack stores the value unchanged. - Start
currentMinatval. If the stack was empty,valis the only value, so it is also the smallest. - If
minStackisn't empty, replacecurrentMinwith the smaller of itself and the top ofminStack. The top is already the minimum of everything below, so one comparison withMath.Minis enough. - Push
currentMinontominStack. Now both stacks have the same height, and equal values are recorded each time they are pushed. - In
Pop, pop from both stacks, one line each. They must stay the same size, or the entries stop lining up. - In
Top, returnstack.Peek().Peekreads the top; onlyPopremoves it. - In
GetMin, returnminStack.Peek(). The answer is already stored.
The solution in C#
class MinStack {
Stack<int> stack = new Stack<int>();
Stack<int> minStack = new Stack<int>();
public void Push(int val) {
stack.Push(val);
int currentMin = val;
if (minStack.Count > 0) {
currentMin = Math.Min(currentMin, minStack.Peek());
}
minStack.Push(currentMin);
}
public void Pop() {
stack.Pop();
minStack.Pop();
}
public int Top() {
return stack.Peek();
}
public int GetMin() {
return minStack.Peek();
}
}
The C# details worth knowing:
Stack<T>API. It lives inSystem.Collections.Generic.Pushadds on top,Popremoves and returns the top,Peekreturns the top without removing it, andCountis a property, not a method, so there are no parentheses.- Empty stacks throw.
PoporPeekon an emptyStack<int>throws anInvalidOperationExceptionwith the message "Stack empty." The tests never do this, which is whyPopcan call both pops without checking. That is also whyminStack.Count > 0is checked beforePeekinPush. Popreturns a value.stack.Pop();on its own line discards the returned value, which is fine here because the method returns nothing.- Fields default to private. The two stacks have no access modifier, so they are private to the class, which is what you want: callers must go through the four methods, or the stacks could drift out of step.
- Extreme values. Comparing never overflows, unlike adding or subtracting. Pushing
int.MinValueand thenint.MaxValuegives aGetMinof-2147483648and aTopof2147483647. - Naming. C# methods use PascalCase (
GetMin), so code ported from another language'sgetMinwill not match the lesson's tests.
Complexity
Time: O(1) per operation. Push does two pushes, one comparison and one Peek. Pop does two pops. Top and GetMin do one Peek each. A .NET Stack<T> is backed by an array, so a push is constant time except on the occasional resize, which averages out to constant (amortized).
Space: O(n). Two stacks, each with one entry per value currently held. The second stack doubles the memory, which is the price of the constant-time minimum.
Edge cases and common mistakes
- One variable for the minimum. It fails after the minimum is popped, because the previous minimum is lost. The second stack exists to keep it.
- Pushing to
minStackonly when a new minimum arrives. That works only if equal values are handled too. Withpush(5), push(5), pop(), a stack that skipped the second 5 would pop the only 5 inminStackand then have nothing to answer with. PushingcurrentMinevery time avoids the issue. - Forgetting one of the two pops. The stacks fall out of step, and
GetMinstarts returning minimums that belong to other depths. - Pushing
valinstead ofcurrentMintominStack.GetMinthen returns the top value, not the smallest. - Confusing
TopandGetMin. After pushing 3, 1, 2,Topis 2 andGetMinis 1. After two pops, only 3 is left and it is both. - Calling the wrong method name.
Push,Pop,Peekare capitalised in C#.pushorpeekwill not compile.
Testing
push(-2), push(0), push(-3), getMin, pop, top, getMingives-3 0 -2.push(5), push(5), push(7), getMin, pop, pop, getMin, topgives5 5 5.push(3), push(1), push(2), top, getMin, pop, pop, getMingives2 1 3.push(int.MinValue), push(int.MaxValue), getMin, topgives-2147483648 2147483647.
