Friday, September 16, 2011

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( );

2 comments:

  1. any way to optimize the second stack?

    ReplyDelete
  2. Yes push value to second stack only if value <= min

    ReplyDelete