Problem overview
You build a class MinStack with four operations: push(value) puts a number on top, pop() removes the top number, top() returns it, and getMin() returns the smallest number currently in the stack. Every operation has to take constant time, and pop, top and getMin are only called on a non-empty stack.
Take the first example: push -2, 0 and -3. The stack holds -2, 0, -3 with -3 on top, so getMin() returns -3. After pop() the stack is -2, 0, so top() returns 0 and getMin() returns -2. The minimum that was removed is gone, and the earlier one is back. The outputs are -3, 0, -2.
Approach
The plain stack operations are easy: a list that you only touch at its end gives O(1) push, pop and top. The trouble is getMin. Scanning the whole stack for the smallest value costs O(n) per call, and with up to 200,000 calls that is far too slow.
Keeping a single variable min does not work either. When the current minimum is popped, you would need the second smallest value, and you have thrown it away.
The fix rests on 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 never change. So the minimum of "this value and everything below it" can be computed once, when the value is pushed, and stored next to it. A second stack, minStack, holds exactly that: its entry at each depth is the smallest value from the bottom up to that depth. Then:
getMinreads the top ofminStack;popremoves the top of both stacks, which uncovers the previous minimum automatically.
This costs one extra number per value, so O(n) space, and every operation stays O(1).
Step by step
- Two stacks. Declare two empty
ArrayDeque<Int>()properties,stackfor the values andminStackfor the running minimums. The end of each deque is the top of the stack. - Push the value. In
push, addvalueto the end ofstack. - Work out the new minimum. Start a
var currentMinatvalue. If the stack was empty, that is already right. IfminStackhas entries, its last entry is the smallest of everything below, so oneminOfcomparison with it gives the minimum of the whole stack includingvalue. - Record it. Add
currentMinto the end ofminStack. Both stacks now have the same size. Equal values are pushed too, so a minimum that was pushed twice is remembered twice. - Pop from both.
popcallsremoveLast()onstackand onminStack. They must stay the same size. - Read the answers.
topreturnsstack.last()andgetMinreturnsminStack.last(). Neither removes anything.
The solution in Kotlin
class MinStack {
val stack = ArrayDeque<Int>()
val minStack = ArrayDeque<Int>()
fun push(value: Int) {
stack.addLast(value)
var currentMin = value
if (minStack.isNotEmpty()) {
currentMin = minOf(currentMin, minStack.last())
}
minStack.addLast(currentMin)
}
fun pop() {
stack.removeLast()
minStack.removeLast()
}
fun top(): Int {
return stack.last()
}
fun getMin(): Int {
return minStack.last()
}
}
Some Kotlin details that matter here:
ArrayDequeis Kotlin's own. Without an import,ArrayDequeiskotlin.collections.ArrayDeque, a growable array used as a double-ended queue.addLast,removeLastandlast()all work at the end in O(1) (amortised for adding).- The parameter is called
value. The task saysval, butvalis a keyword in Kotlin, so it cannot name a parameter. last()on an empty deque throwsNoSuchElementException. That is why the code checksisNotEmpty()before readingminStack.last()inpush. The other methods rely on the guarantee that the stack is not empty.- Parameters are read-only. That is why the code copies
valueinto avarinstead of changing it. valfixes the reference, not the contents.stackis aval, yet the deque still grows and shrinks.
Tracing the first example
The two stacks after each push (the last number is the top), and after the pop:
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 third push getMin() reads -3. After the pop it reads -2, with no search at all. Pushing 0 did not lower the minimum, so the entry for 0 repeats -2.
Complexity
Every operation does a fixed number of deque operations at the end: O(1) time each (adding is amortised O(1) because the backing array occasionally doubles). The two stacks together hold 2n numbers for n values, so the space is O(n).
Edge cases and common mistakes
- A single
minvariable. It breaks on the first pop of the minimum, because the previous minimum is lost. - Forgetting to pop
minStack. The stacks fall out of step andgetMinreturns a minimum for values that are no longer there. - Skipping equal values. Storing a minimum only when it is strictly smaller breaks duplicates: after pushing 5, 5, 7 and popping 7 and one 5, the other 5 must still count. Here every push writes an entry, so this works.
- Extreme values. Values range over the whole
Int. Nothing is added or subtracted, only compared, soInt.MIN_VALUEandInt.MAX_VALUEwork: after pushing both,getMin()returns -2147483648 andtop()returns 2147483647. - Top and minimum differ. In the third example, after pushing 3, 1 and 2,
top()is 2 whilegetMin()is 1. Keep the two roles separate.
Testing
Run the examples against your class in a main of your own. These sequences give these outputs:
- 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.
