Stack with constant time Max() operation

We know that stack has constant time push and pop operation. Now we need to design an solution where we get the max value in stack in constant time.

Problem statement

Design a stack which has constant time push, pop and max operation.

Analysis

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation. First thing we need to do is to keep track of the current max. This would suffice if are never going to pop from the stack. If we pop from the stack, the new remaining stack might have different max. Max in remaining stack can be different if the poped element is max too. 

So we get the first condition : If the poped element is equal to current max value, we need to change the max. 
Again we get the hint : We need to keep track of previous max too. Keep all the elements which were max in stack at any given time. These max values to be stored in such a way that the most recently encountered max can be accessed in O(1) . That’s is our base requirement right? 
Last in first out again? Yes, keep another stack to store max. 

Insertion order : 1,2,3,4,5 then
Main stack : 1,2,3,4,5
Max stack would be : 1,2,3,4,5

Insertion order : 5,4,3,2,1
Main stack  : 5,4,3,2,1
Max stack : 5,5,5,5,5

From the second example we observe that we are unnecessarily storing 5 repeatedly. We can optimize it by storing element in max stack only if max is changed.

Code

Complexity analysis

O(1)  🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s