This is a popular interview question found in a site. (ihas1337code). You need to implement push, pop, min all with just O(1) performance. You can use extra space and you can do any push & pops. Every time you should get the minimum in the stack using the min function.
Do do this, you need 2 stacks. One which maintains all the minimums found until then and one which contains all the numbers.
For example, the main stack is.
The stack with all the min’s found will be
Now, when you pop from the main stack, make sure that you pop the min stack as well only when the element is equal to the popping element.
So, if we have pop-ed 3,2,10, we will still have 1 as min in the min stack. Remove 1 as well in the main stack, you must remove 1 in the min stack as well. Now, definitely 5 is the min.
With this approach, you can implement pop, push, min all in O(1).