Max Stack
Hard · Design · Linked List · Stack · Design · Doubly-Linked List · Ordered Set
Problem
Design a stack that, besides the usual operations, can report and remove its largest element. Implement MaxStack:
- MaxStack() creates an empty stack.
- void push(int x) puts x on top.
- int pop() removes the top element and returns it.
- int top() returns the top element without removing it.
- int peekMax() returns the largest element without removing it.
- int popMax() removes the largest element and returns it. If the largest value appears more than once, remove only the copy closest to the top.
Aim for top in O(1) and every other call in O(log n).
Each test is a list of calls: ops[i] is the method name (the first is the class) and args[i] its arguments. The expected output lists each call’s return value, None for the constructor and push.
Examples
Input: ops = ["MaxStack","push","push","push","push","popMax","top","peekMax","pop","popMax","top"], args = [[],[4],[9],[2],[9],[],[],[],[],[],[]] Output: [None, None, None, None, None, 9, 2, 9, 2, 9, 4]
The first popMax removes the upper 9, leaving [4, 9, 2]. After 2 is popped, popMax removes the other 9 and 4 is on top.
Input: ops = ["MaxStack","push","push","popMax","top"], args = [[],[1],[5],[],[]] Output: [None, None, None, 5, 1]
5 is both the largest and the top, so popMax removes it and 1 is left.
Input: ops = ["MaxStack","push","push","push","pop","peekMax","popMax","top"], args = [[],[3],[1],[7],[],[],[],[]] Output: [None, None, None, None, 7, 3, 3, 1]
Popping 7 also takes it out of the running for the maximum, which becomes 3; popMax then removes 3 from the bottom, and 1 is on top.
Constraints
- -10^7 <= x <= 10^7
- At most 10^5 calls are made in total
- pop, top, peekMax and popMax are only called when the stack is not empty
Approaches
- Plain list, scan for the maximum — time O(1) push/pop/top, O(n) peekMax/popMax, space O(n)
Follow-up
A balanced tree keyed by (value, id) together with a doubly linked list of the pushes gives the same bounds without lazy deletion: the tree finds the largest entry and the list node it points to is unlinked in O(1). Lazy deletion trades that bookkeeping for memory, since removed entries stay in the other structure until they surface; each entry is still discarded at most once, so the cost per call stays O(log n) on average.
Related problems
Start free on Cariara · Coding problems · System design studio
