Implement A Max Stack - A Stack With A .max() API (Similar To Min Stack on LeetCode) @BackToBackSWE
Implement A Max Stack - A Stack With A .max() API (Similar To Min Stack on LeetCode)  @BackToBackSWE
Uploaded January 2019 | Updated November 2026, 3 hours ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: 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: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 9.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
Implement A Max Stack - A Stack With A .max() API (Similar To Min Stack on LeetCode)All Nodes Distance K In A Binary Tree - Performing Bidirectional Search On A Tree Using A HashtableNetwork Flows: Max-Flow Min-Cut Theorem (& Ford-Fulkerson Algorithm)Coding Interview | Terms to know | API & ADT  #shorts #datastructures #codinginterviewMerge K Sorted Arrays - Min Heap Algorithm (Merge K Sorted Lists on LeetCode)Lowest Common Ancestor Between 2 Binary Tree Nodes (A Recursive Approach)Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions4 Tips To Learn Java Programming As Fast As Possible As A BeginnerProfessor Clyde Kruskal On Kruskals AlgorithmPartition To K Equal Sum Subsets From An Array of Integers - The Backtracking ApproachAdd Two Numbers Without The + Sign (Bit Shifting Basics)Compute The Next Permutation of A Numeric Sequence - Case Analysis (Next Permutation on Leetcode)
Back To Back SWE |

Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode)

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER