DSA problem
Max Stack
Design a max stack data structure that supports the stack operations push, pop, top, plus two extras: peekMax returns the maximum element in the stack, and popMax retrieves and removes the maximum element. If there is more than one maximum, only remove the top-most one.
The hard part is popMax. A normal stack with an auxiliary max-stack handles peekMax in O(1), but popMax must remove an arbitrary element from the middle of the main stack and still preserve the original push order of every other element. That rules out simple array-of-pairs solutions for O(log n) targets.
The optimal solution uses two ordered sets (TreeSets) of (value, id) pairs, where id is a monotonically increasing counter assigned on each push. The first set, ordered by id, mirrors the stack order — its largest entry is the current top. The second set, ordered by (value, id), lets us find the maximum (largest value, breaking ties by largest id so we get the top-most). Both sets store the same pairs, so removing one entry costs O(log n) in each set.
push inserts (val, ++id) into both sets. pop removes the last entry of the main set and the matching entry from the max set. top peeks the last entry of the main set. peekMax peeks the last entry of the max set. popMax removes the last entry of the max set (largest value, top-most among ties) and the matching entry from the main set. Every operation runs in O(log n).
Examples
["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"]
[[],[5],[1],[5],[],[],[],[],[],[]][null,null,null,null,5,5,1,5,1,5]["MaxStack","push","push","peekMax","popMax","top"]
[[],[2],[7],[],[],[]][null,null,null,7,7,2]["MaxStack","push","push","push","popMax","popMax","popMax"]
[[],[3],[3],[3],[],[],[]][null,null,null,null,3,3,3]Constraints
- -10^7 <= x <= 10^7
- At most 10^4 calls will be made to push, pop, top, peekMax, and popMax.
- There will be at least one element in the stack when pop, top, peekMax, or popMax is called.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.