Max Stack
Asked at Walmart
Problem
Design a stack that supports push, pop, top, peekMax, and popMax operations. Implement the MaxStack class with O(1) time complexity for all operations. The popMax operation removes and returns the maximum element from the stack.
Asked At
| Company | Difficulty | |
|---|---|---|
| Walmart | HARD | View all Walmart questions → |
How to Think About It
Naive approach: use a single stack. popMax requires scanning the entire stack — O(n) for popMax.
Use two stacks: one for normal operations and a second stack tracking the maximum at each level.
For O(1) popMax, use a doubly linked list to maintain insertion order and a balanced BST (or sorted map) for O(1) access to max.
Alternatively, use a single doubly linked list where each node has a value, plus a HashMap from value to a sorted set of nodes. Push appends to the list and adds to the map.
popMax looks up the max key in the map, removes the last node with that value from the sorted set, removes it from the linked list, and returns the value.
Optimal Approach
Use a doubly linked list to store elements in insertion order, and a TreeMap (balanced BST) mapping each value to a SortedSet of list nodes with that value. Push appends a node to the list and inserts it into the map. Top returns the tail of the list. PeekMax returns the last key in the TreeMap. Pop removes the tail of the list and its entry from the map. PopMax retrieves the largest key, removes the last node in its set, and removes that node from the list. All operations are O(1) amortized.
What Trips People Up in Real Interviews
Ask whether duplicate maximum values are possible (yes). Clarify that popMax removes one occurrence.
Discuss the tradeoff between simplicity (two stacks, O(n) popMax) and optimality (doubly linked list + sorted map, O(1) all ops).
If using the linked list approach, clearly define the data structures: a doubly linked list for order, a TreeMap/SortedDict for values.
Walk through push, pop, popMax with an example to verify correctness.
Mention that in practice, the two-stack approach is often sufficient and easier to implement.
Solution Code
class Node:
def __init__(self, val=0, prev=None, nxt=None):
self.val = val
self.prev = prev
self.nxt = nxt
class MaxStack:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.nxt = self.tail
self.tail.prev = self.head
self.nodes = {}
self.sorted_vals = {}
def push(self, x):
node = Node(x, self.tail.prev, self.tail)
self.tail.prev.nxt = node
self.tail.prev = node
self.nodes[id(node)] = node
if x not in self.sorted_vals:
self.sorted_vals[x] = set()
self.sorted_vals[x].add(id(node))
def pop(self):
node = self.tail.prev
val = node.val
self.tail.prev = node.prev
node.prev.nxt = self.tail
del self.nodes[id(node)]
self.sorted_vals[val].discard(id(node))
if not self.sorted_vals[val]:
del self.sorted_vals[val]
return val
def top(self):
return self.tail.prev.val
def peekMax(self):
return max(self.sorted_vals.keys())
def popMax(self):
val = max(self.sorted_vals.keys())
node_id = self.sorted_vals[val].pop()
if not self.sorted_vals[val]:
del self.sorted_vals[val]
node = self.nodes[node_id]
node.prev.nxt = node.nxt
node.nxt.prev = node.prev
del self.nodes[node_id]
return valFrequently Asked Questions
What is the Max Stack problem?
Design a stack that supports push, pop, top, peekMax, and popMax operations. Implement the MaxStack class with O(1) time complexity for all operations. The popMax operation removes and returns the maximum element from the stack.
How do you solve Max Stack?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Max Stack?
Max Stack is asked at Walmart. It is a hard difficulty problem.
What are common mistakes on Max Stack?
- Ask whether duplicate maximum values are possible (yes). Clarify that popMax removes one occurrence.
- Discuss the tradeoff between simplicity (two stacks, O(n) popMax) and optimality (doubly linked list + sorted map, O(1) all ops).
- If using the linked list approach, clearly define the data structures: a doubly linked list for order, a TreeMap/SortedDict for values.
- Walk through push, pop, popMax with an example to verify correctness.
- Mention that in practice, the two-stack approach is often sufficient and easier to implement.