Problem overview
A stack gives values back in reverse order: the last value pushed is the first one popped. The task is to build a MinStack class that also answers "what is the smallest value in the stack right now?" through getMin(), and to make every operation (push, pop, top and getMin) run in constant time.
The calls are applied in order to one new MinStack, and the results of top and getMin are listed. Take the first example: push -2, push 0, push -3. The stack holds -2, 0, -3 with -3 on top, so getMin() is -3. After pop() the stack is -2, 0: top() is 0 and getMin() is -2 again. The output is -3 0 -2.
The lesson's tests only call pop, top and getMin on a non-empty stack, so the code doesn't need to handle an empty one.
Approach: remember the minimum next to each value
The obvious way to answer getMin is to look through the whole array, which costs O(n) per call. With up to 200,000 calls, that is too slow. Keeping a single min variable fails differently: when the minimum is popped, the variable would have to be recomputed, and that is the same O(n) scan.
The way out comes from one observation. A value leaves the stack only after every value above it has left. While it is in the stack, the values below it can't change. So the minimum of "this value and everything below it" is known at the moment of the push and stays correct for as long as that value exists. Write it down once, next to the value.
The class therefore keeps two arrays of the same length:
stackholds the values, with the top of the stack at the end of the array;minStackholds, at each depth, the smallest value from the bottom up to that depth.
Pushing 3, 1, 2 gives stack = [3, 1, 2] and minStack = [3, 1, 1]. The last entry of minStack always describes the whole stack, so getMin only reads it. Popping removes the last entry of both arrays, which uncovers the minimum the stack had before that value arrived. In the first example, popping -3 leaves minStack = [-2, -2], and the answer -2 is already there.
Step by step
- Declare
stackas avarof type[Int], set to an empty array. It has to be avarbecause the methods change it, and appending to or removing from the end of an array is cheap. - Declare
minStackthe same way, for the running minimums. - In
push, append the value tostackfirst, as on any stack. - Start
currentMinatval. If the stack was empty,valis its only value and so its minimum. It is avarbecause the next step may lower it. - If
minStackisn't empty, comparecurrentMinwith the top ofminStackand keep the smaller. That top entry is already the smallest value underval, so one comparison is enough. - Append
currentMintominStack. Both arrays now have the same length. Equal values are pushed too, so a minimum pushed twice is remembered twice. - In
pop, remove the last element of both arrays, so they stay the same size. - In
top, return the last element ofstack. - In
getMin, return the last element ofminStack.
The solution in Swift
class MinStack {
var stack: [Int] = []
var minStack: [Int] = []
func push(_ val: Int) {
stack.append(val)
var currentMin = val
if !minStack.isEmpty {
currentMin = min(currentMin, minStack.last!)
}
minStack.append(currentMin)
}
func pop() {
stack.removeLast()
minStack.removeLast()
}
func top() -> Int {
return stack.last!
}
func getMin() -> Int {
return minStack.last!
}
}
The Swift details worth a closer look:
lastis an optional.array.lasthas typeInt?, and it isnilfor an empty array. The!unwraps it and crashes the program if it isnil. Here that is safe, because the tests never calltoporgetMinon an empty stack, andpushchecksisEmptybefore usingminStack.last!.removeLast()also needs a non-empty array. On an empty array it stops the program with a run-time error. Its result is the removed element, andpopignores it. Swift accepts that becauseremoveLast()is marked to allow an unused result.- The free function
min. Inside the class,min(currentMin, minStack.last!)calls Swift's globalminon twoIntvalues. The class has no method of that name, so there is no clash. - A class, not a struct. The methods change
stackandminStack. In a struct they would need to be markedmutating. A class is a reference type, so its methods can change its stored properties directly. - The type annotations.
var stack: [Int] = []says which kind of array the empty literal is. Without the annotation the compiler can't tell.
Complexity
Time: O(1) per operation. push does one comparison and two appends. pop removes two last elements. top and getMin read one last element. An append is amortized constant: now and then the array has to grow, but the cost averages out over many pushes.
Space: O(n). For n values in the stack there are n entries in each array, so twice as many integers as a plain stack. That is the price of making getMin constant-time.
Edge cases and common mistakes
- Keeping one
minvariable. It works until the minimum is popped. Then the previous minimum is lost, and finding it again means scanning the stack. - Duplicate minimums. Push 5, 5, 7 and the arrays are
[5, 5, 7]and[5, 5, 5]. After two pops, the stack still holds one 5, andgetMin()gives 5. A version that pushes to the minimum stack only when a value is strictly smaller would lose the second 5 and answer wrongly here. - Forgetting to pop from both arrays. The two arrays must always have the same length. If
poponly touchesstack,getMinreturns a minimum that is no longer in the stack. - Top and minimum are different things. After pushing 3, 1, 2,
top()is 2 andgetMin()is 1. - Extreme values. Values range over the whole 32-bit signed range, and Swift's
Intis 64 bits, so-2147483648and2147483647fit with room to spare. The code only compares values, and never adds them.
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 -2147483648 and 2147483647:
getMin()is -2147483648 andtop()is 2147483647. - Push 3, 1, 2: the arrays are
[3, 1, 2]and[3, 1, 1].
