Retrieving the Min element in a stack in O(1) Time

Question

The reason I'm asking this question is because I cannot see why the way I think cannot be applied to this particular question

"How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time"

My basic solution: Wouldn't it be possible if we had a variable in stack class, that whenever we were pushing an item to stack we would check if it is smaller than our min variable. If it is assign the value to the min, if not ignore.

You would still get the O(1) as the min function would be;

int getMinimum(){
  return min;
}

Why this solution is never mentioned, or what is the fault with the way I think?

Answer 1

This wouldn't work if you popped numbers off the stack.

Ex. 2,4,5,3,1. After you pop 1 off, what is your minimum?

The solution is to keep a stack of minimums, not just a single value. If you encounter a value that is less than equal to the current minimum, you need to push it onto the min-stack.

Ex.

Push(4):
Stack: 4
Min-stack: 4

Push(2):
Stack: 4 2
Min-stack: 4 2

Push(2):
Stack: 4 2 2
Min-stack: 4 2 2

Push(5):
Stack: 4 2 2 5
Min-stack: 4 2 2

Push(3):
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Push(1):
Stack: 4 2 2 5 3 1
Min-stack: 4 2 2 1

Pop():
Stack: 4 2 2 5 3
Min-stack: 4 2 2

Pop():
Stack: 4 2 2 5
Min-stack: 4 2 2

Pop():
Stack: 4 2 2
Min-stack: 4 2 2

Pop():
Stack: 4 2
Min-stack: 4 2

Pop():
Stack: 4
Min-stack: 4