Question 7: How would you design a stack such that, in addition to push() and pop(), has a function min() which returns the minimum element? Push, pop, and min should all operate in O(1) time.
At first glance, it’s easy to think that we will need to create a lot of modifications to the Stack class, but the minimum element does not change that often. Just when a smaller element is added.
One solution is to define a variable minValue
, which carries the minimum element. Whenever this element is removed from the stack, we search through the stack to find the minimum element. This will take a long time to execute.
push(5); stack is {7}, min is 7
push(6); stack is {9, 7}, min is 7
push(3); stack is {3, 9, 7}, min is 3
push(8); stack is {8, 3, 9, 7}, min is 3
pop(); pops 8. stack is {3, 9, 7}, min is 3
pop(); pops 3. stack is {9, 7}. min is 7.
Every time the min element is updated, it corresponds to a new state in the Stack. We can utilize this to efficiently find the new min by storing the min at every state of the Stack. If a push() results in a new min, we store the new min value. If a pop() results in a new min, we can revert back to a previous min value. Essentially we can define a second stack, call it mins
, which contains a history of past mins and the current min at the top level of the stack.
We’re done!