Stack with constant time max operation
Design a stack which has constant time push, pop and 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. To understand more about stack data structure please refer : stack data structure.
Constant time max operation in stack
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 popped 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.
Stack with constant time find max operation
Complexity of all operations is O(1).
Please share if there is something missing or wrong. If you want to contribute to website, please contact us.