Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Design a stack that includes a max operation, in addition to push and pop. The max method should return the maximum value stored in the stack.
A stack is an abstract data type (ADT).
An ADT is a data type is defined by its behavior from the point of view of a user of the data, we can implement it however we want as long as we give the user the interface they need to get what they expect from the ADT.
Stack is LIFO since the last item to go in, is the first one to come out.
Here we are asked to implement a stack with a max API which entails.
push()
Add an element
pop()
Get the top element
max()
Get the maximum element
The reason this is a problem is because the stack ADT restricts how data is added and retrieved from the structure so to make the .max() function run optimally we will have to think a little harder than the first approach we think of.
Approach 1 (No Optimizations & Obvious)
To answer a call to .max() we can iterate through the whole structure supporting our stack underneath and return the maximum item
whether it is implemented with an array, a lined list, etc.
This will take O(n) "linear" time always and O(1) "constant" space
Approach 2 (Use Auxiliary Data Structures)
We can use a max heap or a Binary Search Tree in tandem with a hashtable for fast lookups.
This idea is critical. Auxiliary structures with a hash table backing your ordered structures for quick lookups to get immediate reference to objects.
The structure solves the problem.
The hashtable let's you get into it fast.
This can bring us to log(n) time, but worsens space to O(n) since we will store at max all items potentially.
Approach 3 (Remember The Max At Each Element)
Write the optimal code [in EPI], but walkthrough this first.
On push it is easy to know what the max is if we have a global variable knowing the max.
We just compare the item we are adding to that max.
If the pushed item is greater then we update the global variable.
If the pushed item is less then we do nothing to the global variable.
On pop there is a problem, if we pop the element that was the maximum in the stack to that point, we have no idea what the next maximum item is unless we do an O(n) scan to restore the global variable.
So the solution is to remember the maximum in the stack at or below each item.
IF WE REMEMBER THE MAX AT EACH PUSH THEN WE SOLVE THE PROBLEM OF BEING LOST ON POP.
Complexities
Time: O( 1 )
.max() knows the maximum immediately
Space: O( n )
We need to store the max on every element upping our space usage
BIG TWEAK
We can improve the best case.
Notice that if a pushed element is less than the maximum, then it can never be the maximum.
We will use an auxiliary stack to record historical maximums and its count of occurrences (we can't just store the raw values becase of possible duplicates).
Complexities
Time stays O( 1 ), we are just optimizing space
Worst case space stays O( n )
If each pushed item is a max and needs a cached max entry
But best case for space becomes O(1) best case if the max does not change frequently.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 9.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
