Stack class with Push, Pop, and Min in Constant Time

By | May 24, 2014

This is a commonly asked interview question .The problem is like this

Design a stack class that supports push, pop, and min ( retrieving the minimum element ) operations in constant time

The problem can be solved easily using an extra stack (MinStack) .On each min call you just have to return the element the element on top of MinStack.
Algorithm

  • for each min() call simple return the element on top of MinStack
  • On each push operation do this
    • push the element on original Stack
    • if(MinStack.top()
    • else push elementToPush on Minstack
  • On each pop operation pop an element from both the stacks

Here’s the code

Leave a Reply

Your email address will not be published. Required fields are marked *