Problem overview
The class MinStack behaves like an ordinary stack: push puts an integer on top, pop removes the top value, and top reads it without removing it. It has one extra operation, getMin, which returns the smallest value currently in the stack. Every operation must run in constant time, and pop, top and getMin are only called on a non-empty stack.
Take the first example: push -2, push 0, push -3. The stack holds -2, 0 and -3, with -3 on top, so getMin() gives -3. After pop() the stack holds -2 and 0, so top() gives 0 and getMin() gives -2. The output is -3 0 -2. The third example shows that the top and the minimum are different questions: after pushing 3, 1 and 2, the top is 2 and the minimum is 1.
Approach: remember the minimum under every value
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 need the second smallest, and finding it means scanning again.
The fix is to record the answer while the information is available. A value leaves the stack only after every value above it has left, so the values below it cannot change while it is in the stack. The smallest value from the bottom up to a given position can therefore be computed once, when that position is pushed, and never changes.
So the class keeps two stacks of equal height. The first holds the values. The second holds, at each depth, the smallest value from the bottom up to that depth. The top of the second stack always describes the whole stack as it is now. Popping removes the top of both, and the minimum from before that value arrived is uncovered automatically.
Pushing -2, 0 and -3 builds these two stacks, bottom first:
push(-2): stack=List(-2) minStack=List(-2)
push(0): stack=List(-2, 0) minStack=List(-2, -2)
push(-3): stack=List(-2, 0, -3) minStack=List(-2, -2, -3)
After the pop, the top of minStack is -2 again, which is exactly what the example expects.
Step by step
- Declare the value stack as a
valholding ascala.collection.mutable.Stack[Int]. Thevalfixes which stack the name refers to, while the stack itself stays mutable. - Declare the second stack the same way, as
minStack. It will always have as many entries asstack. - Start
push. The parameter is calledvaluebecausevalis a Scala keyword. First put the value onstack. - Start the candidate minimum in a
varcalledcurrentMin, set tovalue. If the stack was empty, that value is the only one and so the smallest. - Compare with what is below. If
minStackis not empty, its top is already the smallest of everything underneath, so onemath.minagainst it is enough. - Push
currentMinontominStack. Equal values are pushed too, so a minimum that was pushed twice is remembered twice. - Write
pop. Pop both stacks, one line each, so they stay the same height. - Write
top. It returns the top ofstackwithout removing it. - Write
getMin. It returns the top ofminStack.
The solution in Scala
class MinStack {
val stack = scala.collection.mutable.Stack[Int]()
val minStack = scala.collection.mutable.Stack[Int]()
def push(value: Int): Unit = {
stack.push(value)
var currentMin = value
if (minStack.nonEmpty) {
currentMin = math.min(currentMin, minStack.top)
}
minStack.push(currentMin)
}
def pop(): Unit = {
stack.pop()
minStack.pop()
}
def top(): Int = {
return stack.top
}
def getMin(): Int = {
return minStack.top
}
}
The Scala details worth a closer look:
mutable.Stack. Scala's default collections are immutable, so the code names the mutable one in full.pushandpop()work at the top, andtopreads the top without removing it. Printing a stack lists the top first: after pushing 1, 2 and 3,println(stack)showsStack(3, 2, 1).- Constructing without
new.Stack[Int]()calls the companion object'sapply, which builds an empty stack of integers. returnis optional. The last expression of a method is its value, sostack.topalone would do intopandgetMin. The lesson's code spellsreturnout, which is also correct.Unit.pushandpopreturnUnit, Scala's "nothing useful" result. The stack's ownpop()returns the removed value, but the lesson'spopmethod does not pass it on.Intcovers the range. The values go up to 2^31 - 1, the largestInt, and down to -2^31.math.minonly compares, so nothing overflows: pushingInt.MaxValueand thenInt.MinValuegives agetMinof -2147483648 and atopof -2147483648, and after one popgetMinis 2147483647.- Empty stacks throw. Calling
topon an emptymutable.Stackraisesjava.util.NoSuchElementException: head of empty Stack. The lesson promises never to do that, so no check is needed.
Complexity
Time: O(1) per operation. push does two stack pushes and one comparison, pop two pops, and top and getMin one read each. None of them looks at more than the top of a stack.
Space: O(n). For n values in the stack, the second stack holds n more integers. That is twice the memory of a plain stack, which is the price for constant-time minimums.
Edge cases and common mistakes
- Duplicate minimums. Pushing 5, 5 and 7 and then popping twice leaves a 5, so the minimum is still 5. Because
minStackgets an entry for every push, each copy of the 5 has its own record. A design that stored the minimum only when it strictly decreases would lose the second 5 and answer wrongly here. - Top and minimum are different. After pushing 3, 1, 2, the top is 2 and the minimum is 1. Returning one for the other fails the third example.
- Forgetting to pop
minStack. The stacks fall out of step, andgetMinreports a minimum that has already left. - A single variable for the minimum. It works until the minimum is popped, and then has nothing to fall back on.
- A single element. With one value pushed,
topandgetMinboth return it. ThenonEmptycheck is what keepspushfrom reading an emptyminStack.
Testing
Using one new MinStack for each line, the outputs of top and getMin in order are:
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()gives5 5 5.push(3), top(), getMin(), push(1), push(2), top(), getMin(), pop(), pop(), getMin()gives3 3 2 1 3.
