Leetcode 716. Max Stack
Asked at:
Confluent
DESCRIPTION
Design a Max Stack data structure that supports standard stack operations (push, pop, top) plus two additional operations: peekMax (return the maximum element) and popMax (remove and return the most recently added maximum element). The key challenge is efficiently handling popMax when the maximum isn't at the top of the stack. For example, if the stack contains [5, 1, 5] (bottom to top), calling popMax() should remove the second 5 (most recent), leaving [5, 1].
Input:
stack = MaxStack() stack.push(5) stack.push(1) stack.push(5) stack.peekMax() # returns 5 stack.popMax() # returns 5 stack.top() # returns 1
Output:
peekMax() → 5 popMax() → 5 top() → 1
Explanation: After pushing [5, 1, 5], peekMax() finds the maximum 5. popMax() removes the most recent 5 (at top), leaving [5, 1]. top() now returns 1.
Constraints:
- All operations should be as efficient as possible
- Handle duplicate maximum values correctly (remove most recent)
- Support standard stack semantics for push, pop, and top
- Values can be any integers (positive, negative, or zero)
Understanding the Problem
The core challenge is maintaining two orderings simultaneously: stack order (LIFO) and maximum order (sorted by value, then by recency). A naive approach using a single array requires O(n) time to find and remove the maximum. The popMax operation is particularly tricky because it must remove an element from the middle of the stack while preserving the relative order of other elements. We need data structures that support efficient lookup by both position (for stack ops) and value (for max ops).
Building Intuition
A naive approach using a single list requires scanning all elements to find the maximum (O(n) for peekMax and popMax). A better approach uses two data structures: a stack for LIFO order and a max heap (or sorted structure) for tracking maximums. However, heaps don't support efficient arbitrary deletion. The optimal solution combines a doubly-linked list (for O(1) deletion at any position) with a TreeMap/balanced BST (for O(log n) max lookup and removal). Each element stores its position in both structures. For example, pushing 5, 1, 5 creates nodes in the list and entries in the TreeMap mapping 5 → [node1, node3], 1 → [node2].
This pattern appears in real-time monitoring systems (tracking current max metric while maintaining history), undo/redo stacks with priority (undo highest-priority action), and trading systems (process orders in LIFO but also need to cancel highest-value orders). Understanding how to maintain multiple orderings efficiently is crucial for building responsive systems that need both temporal and value-based access patterns.
Common Pitfalls
Implementation
Doubly-Linked List for Stack Storage
Implement a doubly-linked list node and list structure to store stack elements with O(1) insertion and deletion at any position. Each node contains a value, timestamp (for recency tracking), and pointers to previous/next nodes. The list maintains head and tail pointers for efficient stack operations. For example, pushing 5, 1, 5 creates three linked nodes where each can be removed in O(1) time given its reference. This structure serves as the foundation for both stack operations and the max-tracking mechanism in the next section.
class Node:def __init__(self, val):self.val = valself.prev = Noneself.next = Noneclass DoublyLinkedList:def __init__(self):self.head = Noneself.tail = Nonedef append(self, val):node = Node(val)if not self.tail:self.head = self.tail = nodeelse:self.tail.next = nodenode.prev = self.tailself.tail = nodereturn nodedef remove(self, node):if node.prev:node.prev.next = node.nextelse:self.head = node.nextif node.next:node.next.prev = node.prevelse:self.tail = node.prev
TreeMap for Maximum Tracking
Build a TreeMap (balanced BST) that maps each value to a list of node references ordered by insertion time (most recent last). This enables O(log n) lookup of the maximum key and O(log n) removal of the most recent node with that value. For example, after pushing [5, 1, 5], the TreeMap contains {5: [node1, node3], 1: [node2]}. When popMax() is called, retrieve the maximum key 5, pop the last node reference node3 from its list, and remove node3 from the doubly-linked list built in Section 1. This section uses the node structure from Section 1 to maintain the max-tracking index.
import bisectclass TreeMap:def __init__(self):self.keys = [] # sorted list of unique valuesself.map = {} # value -> list of Node referencesdef add(self, val, node):if val not in self.map:bisect.insort(self.keys, val)self.map[val] = []self.map[val].append(node)def get_max(self):return self.keys[-1] if self.keys else Nonedef pop_max_node(self):max_val = self.keys[-1]node = self.map[max_val].pop()if not self.map[max_val]:del self.map[max_val]self.keys.pop()return node
Complete MaxStack Integration
Combine the doubly-linked list from Section 1 and TreeMap from Section 2 into a unified MaxStack class that exposes the five required operations. The class maintains both structures in sync: push(x) creates a new node, appends it to the list tail, and adds its reference to the TreeMap under key x. pop() removes the tail node and updates the TreeMap. popMax() uses the TreeMap to find the maximum value's most recent node, removes it from both structures, and returns its value. For example, a complete workflow of push(5), push(1), push(5), popMax() demonstrates how both structures stay synchronized through each operation.
class MaxStack:def __init__(self):self.dll = DoublyLinkedList()self.tree = TreeMap()def push(self, x):node = self.dll.append(x)self.tree.add(x, node)def pop(self):node = self.dll.tailval = node.valself.dll.remove(node)self.tree.map[val].remove(node)if not self.tree.map[val]:del self.tree.map[val]self.tree.keys.remove(val)return valdef top(self):return self.dll.tail.valdef peekMax(self):return self.tree.get_max()def popMax(self):node = self.tree.pop_max_node()val = node.valself.dll.remove(node)return val
What We've Learned
- Pattern: Maintain dual data structures (linked list + TreeMap) when you need efficient access by both position and value - each structure optimizes different operations
- Use Case: Apply this to priority undo stacks, real-time metric tracking, or any system requiring both temporal order and value-based queries
- Technique: Use doubly-linked lists for O(1) arbitrary deletion and balanced BSTs for O(log n) sorted access - store cross-references between structures
- Recency Handling: Track insertion order for duplicates using timestamps or lists of references ordered by insertion time to correctly identify the most recent maximum
Problems to Practice
Monotonic stacks are directly relevant to Max Stack as they maintain ordering properties while supporting stack operations. This lesson teaches how to maintain additional invariants (like maximum values) alongside standard stack behavior, which is the core challenge in Max Stack.
Heaps are a key data structure for efficiently tracking maximum elements, which is central to implementing popMax and peekMax operations in O(log n) time. Understanding heap operations complements the stack-based approach and provides insight into the dual data structure solution commonly used for Max Stack.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late June, 2026
Mid-level
Early April, 2026
Staff
Late March, 2026
Staff
Hello Interview Premium
Your account is free and you can post anonymously if you choose.