Problem overview
A stack gives values back in last-in, first-out order. The task is to build a MinStack that also reports the smallest value it currently holds. It has four operations besides new: push(val) adds an i32, pop() removes the top value, top() returns the top value, and get_min() returns the smallest value in the stack. Every operation must run in constant time. The calls to pop, top and get_min only happen on a non-empty stack, so the code doesn't have to handle an empty one.
In the first example the values -2, 0 and -3 are pushed, so get_min() is -3. After pop() removes -3, top() is 0 and get_min() is -2 again. The interesting part is that last answer: when the minimum leaves the stack, the structure has to remember what the minimum was before it arrived.
Approach: remember the minimum at every depth
The simplest get_min scans the whole vector for its smallest element. That costs O(n) per call, which the lesson forbids. Keeping a single variable min doesn't work either: it is easy to update on a push, but after a pop there is nothing to tell what the next smallest value is.
The way out is an observation about stacks. A value can leave only after every value above it has left, so the values below it don't change while it is in the stack. The smallest value from the bottom up to any given position is therefore fixed at the moment that position is pushed, and it can be written down once.
So the struct keeps two vectors of the same length. stack holds the values. min_stack holds, at each depth, the smallest value from the bottom up to that depth. A push computes its entry from the previous top of min_stack with one comparison, and a pop removes the top of both vectors. The minimum of the whole stack is always the top entry of min_stack.
Here are both vectors during the first example (the end of each vector is the top):
push -2 stack [-2] min_stack [-2]
push 0 stack [-2, 0] min_stack [-2, -2]
push -3 stack [-2, 0, -3] min_stack [-2, -2, -3]
pop stack [-2, 0] min_stack [-2, -2]
After the pop, top() returns 0 and get_min() returns -2, with no search at all. The pop uncovered the entry that was already there.
A common alternative stores only the values that set a new minimum, in a smaller second stack. It saves some memory on average, but it needs care with duplicates. This lesson pushes one entry per value, which is simpler and always correct.
Step by step
- Declare the
stackfield as aVec<i32>. A vector adds, reads and removes at its end in constant time, so the end is the top of the stack. - Declare the
min_stackfield, also aVec<i32>. Its entry at each depth is the smallest of the value at that depth and everything below it. - Write
newso that it returns aMinStackholding two empty vectors. The struct expression is the last thing in the function and has no semicolon, so it is the return value. - In
push, addvaltostack. The value goes on the ordinary stack as it would on any stack. - Start
current_minatval, declared withlet mut. If the stack was empty,valis its only value and so its smallest. - If
min_stackisn't empty, lowercurrent_minto the smaller of itself and the top ofmin_stack. One comparison is enough because that top already summarizes everything below. - Push
current_minontomin_stack. Both vectors now have the same length. Equal values are pushed too, so a minimum that was pushed twice is remembered twice. - In
pop, pop both vectors. They must stay the same size. Removing the top ofmin_stackuncovers the minimum from before the removed value arrived. - In
top, return the last element ofstackwithout removing it. - In
get_min, return the last element ofmin_stackin the same way.
The solution in Rust
struct MinStack {
stack: Vec<i32>,
min_stack: Vec<i32>,
}
impl MinStack {
fn new() -> MinStack {
MinStack { stack: Vec::new(), min_stack: Vec::new() }
}
fn push(&mut self, val: i32) {
self.stack.push(val);
let mut current_min = val;
if !self.min_stack.is_empty() {
current_min = current_min.min(*self.min_stack.last().unwrap());
}
self.min_stack.push(current_min);
}
fn pop(&mut self) {
self.stack.pop();
self.min_stack.pop();
}
fn top(&self) -> i32 {
*self.stack.last().unwrap()
}
fn get_min(&self) -> i32 {
*self.min_stack.last().unwrap()
}
}
The Rust details worth a closer look:
last()returns anOption<&i32>. It isNonefor an empty vector and a reference to the final element otherwise.unwrap()takes the reference out, which is safe here because the lesson only callstopandget_minon a non-empty stack. The leading*reads thei32behind the reference, which is what the function returns.pop()returns anOptiontoo. The callself.stack.pop();drops the removed value, which is fine because this lesson'spopreturns nothing. On an empty vector it returnsNoneand does nothing.minis a method on integers.current_min.min(other)returns the smaller of the twoi32values.&mut selfand&self.pushandpopchange the struct, so they take&mut self.topandget_minonly read it, so&selfis enough, and the compiler enforces the difference.- Final expressions.
MinStack { ... },*self.stack.last().unwrap()and the other returned values have no semicolon. Adding one would turn the expression into a statement, and the function would no longer return its value.
Complexity
Time: O(1) per operation. push does two vector pushes (amortized constant time) and one comparison. pop does two vector pops. top and get_min read one element. None of them loops over the stack.
Space: O(n). The two vectors each hold one number per value on the stack, so the memory is twice what a plain stack needs, which is still linear in the number of values.
Edge cases and common mistakes
- Duplicate minimums. After pushing 5, 5 and 7,
min_stackis[5, 5, 5]. Two pops leave a stack of one 5, andget_min()is still 5. A design that stored a minimum only when it was strictly smaller would lose the second 5 and answer wrongly here. - Top and minimum differ. After pushing 3, 1 and 2,
top()is 2 andget_min()is 1. After two pops only 3 is left, andget_min()is 3. - Forgetting to pop
min_stack. Ifpopremoves only fromstack, the two vectors fall out of step andget_minkeeps reporting a value that has left the stack. - Extreme values. Values are
i32, and the code only compares them and never adds or subtracts, so nothing can overflow. Pushingi32::MINand theni32::MAXgivesget_min()equal to -2147483648 andtop()equal to 2147483647. - Scanning in
get_min. Callingself.stack.iter().min()works but costsO(n)per call, which is the cost this lesson avoids.
Testing
- Push -2, 0, -3, then
get_min,pop,top,get_min: the results are -3, 0, -2. - Push 5, 5, 7, then
get_min,pop,pop,get_min,top: the results are 5, 5, 5. - Push 3, then
topandget_min: both are 3. - Push 3, 1, 2:
topis 2 andget_minis 1. After two pops,get_minis 3.
