Approach #1: Two Stacks [Accepted]
Intuition and Algorithm
A regular stack already supports the first 3 operations, so we focus on the last two.
For peekMax
, we remember the largest value we've seen on the side. For example if we add [2, 1, 5, 3, 9]
, we'll remember [2, 2, 5, 5, 9]
. This works seamlessly with pop
operations, and also it's easy to compute: it's just the maximum of the element we are adding and the previous maximum.
For popMax
, we know what the current maximum (peekMax
) is. We can pop until we find that maximum, then push the popped elements back on the stack.
Our implementation in Python will showcase extending the list
class.
Complexity Analysis

Time Complexity: for the
popMax
operation, and for the other operations, where is the number of operations performed. 
Space Complexity: , the maximum size of the stack.
Approach #2: Double Linked List + TreeMap [Accepted]
Intuition
Using structures like Array or Stack will never let us popMax
quickly. We turn our attention to tree and linkedlist structures that have a lower time complexity for removal, with the aim of making popMax
faster than time complexity.
Say we have a double linked list as our "stack". This reduces the problem to finding which node to remove, since we can remove nodes in time.
We can use a TreeMap mapping values to a list of nodes to answer this question. TreeMap can find the largest value, insert values, and delete values, all in time.
Algorithm
Let's store the stack as a double linked list dll
, and store a map
from value
to a List
of Node
.

When we
MaxStack.push(x)
, we add a node to ourdll
, and add or update our entrymap.get(x).add(node)
. 
When we
MaxStack.pop()
, we find the valueval = dll.pop()
, and remove the node from ourmap
, deleting the entry if it was the last one. 
When we
MaxStack.popMax()
, we use themap
to find the relevant node tounlink
, and return it's value.
The above operations are more clear given that we have a working DoubleLinkedList
class. The implementation provided uses head
and tail
sentinels to simplify the relevant DoubleLinkedList
operations.
A Python implementation was not included for this approach because there is no analog to TreeMap available.
Complexity Analysis

Time Complexity: for all operations except
peek
which is , where is the number of operations performed. Most operations involvingTreeMap
are . 
Space Complexity: , the size of the data structures used.
Analysis written by: @awice.