Design a Data Structure which supports push, pop and findMin operation in O(1).

Solution:

Extra Space:

Use two stack say stack1 and stack2. stack2 is used to keep track of Minimum number in the list at each step.

push( n ):    stack1.push(n);
                 stack2.push( Min( n, stack2.top( ) ) );

pop( ):        stack1.pop( );
                 stack2.pop( );

findMin( ):  stack2.top( );