How do you design a stack that can return its minimum element in constant time?
You keep two stacks side by side. The first one holds the values, and the second one holds the smallest value that was seen up to each point of the first one.
So how does that work? When you push a value on, you also push onto the second stack the smaller of the new value and the value that was already on top of the second stack. So the second stack always has the same number of items as the first one, and the top of the second stack is the minimum of the whole stack.
the values stack the mins stack
----------------- -----------------
push 5 push 5
push 3 push 3
push 7 push 3
the minimum is the top of the mins stack, which is 3
And when you pop a value off, you pop one off each stack. The two stacks always stay the same length, so that is safe.
And the important thing is that the answer is always at the top of the second stack, so getting the minimum is O of 1. That is the whole point of the question.
the operation the time
----------------- ---------
push O(1)
pop O(1)
get the minimum O(1)
And why can you not just keep one number that holds the minimum? Because that is the trap in this question. If you keep one number and a value goes below it and then the value is popped off, you have lost the old minimum and you cannot work it out again. The second stack keeps the history, so when the small value goes away the previous minimum comes back to the top.
And there is a second design that is worth knowing about. You keep one stack where each entry holds the value and the minimum at that point. That is the same idea with the two pieces of information in one entry instead of in two stacks. It uses less memory when the values are small and more when they are large.
So the rule to remember is this. Keep the history of the minimum, not just the minimum itself, and then every operation is constant.
The last question in this topic shows the code.