Design a stack which returns minimum element in constant time

Design a stack to support an additional operation which returns the minimum element from the stack in constant time. The stack should continue supporting all other operations like push, pop, top, size, empty, etc, with no degrade in performance for these operations.


 

The first solution that appears in mind is to have a member variable in a stack to keep track of the minimum number. Unfortunately, this won’t work as we can’t get the next minimum number after the minimum one is popped.

 
The correct approach is to use two stacks – the main stack to store the actual stack elements and an auxiliary stack to store the required elements needed to determine the minimum number in constant time. This implementation requires few changes in push and pop operations:

 

1. Push operation

The idea is to push the new element into the main stack and push it into the auxiliary stack only if stack is empty or the new element is less than or equal to the current top element of the auxiliary stack.

 

2. Pop operation

For pop operation, we remove the top element from the main stack and remove it from the auxiliary stack only if it is equal to the current minimum element. i.e. top element of both main stack and auxiliary stack are same. After the minimum number is popped, the next minimum number appears on the top of auxiliary stack.

 

3. Min operation

The top of the auxiliary stack always returns the minimum number since we are pushing the minimum number into the auxiliary stack and removing the minimum number from the auxiliary stack only if it is removed from the main stack.

 
Below table demonstrates the above operations:

 
Stack Operations

 
This is illustrated below in C++/Java:

C++

Download   Run Code

Java

Download   Run Code

 
Continue Reading: Design a stack which returns minimum element without using auxiliary stack

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Anshul
Guest

Great

qayyum
Guest

Simple test wont run