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.
Design a stack which has constant time push, pop and max operation.
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.