Max Stack

Max Stack

What is this problem about?

The Max Stack problem requires you to design a custom Stack data structure that supports standard stack operations (push, pop, top), as well as two special operations: peekMax() to retrieve the maximum element in the stack without removing it, and popMax() to retrieve and remove the maximum element in the stack. If there are multiple maximum elements, popMax() must remove the one closest to the top of the stack.

Why is this asked in interviews?

This is a premier System Design and Data Structure synchronization question. Interviewers use it to see if a candidate can bridge the gap between LIFO (Last-In-First-Out) operations and Priority (Max) operations. Removing an element from the middle of a stack breaks the core definition of a stack, so candidates must cleverly combine structures to achieve $O(\log N)$ or amortized $O(1)$ time complexities.

Algorithmic pattern used

The most robust approach uses a Doubly-Linked List paired with a TreeMap / Ordered Set.

• The Doubly-Linked List simulates the actual Stack, allowing $O(1)$ push, pop, and top, as well as $O(1)$ removal of any node if you have its reference.
• The TreeMap (or balanced BST) maps value -> List of Nodes. It naturally sorts keys, allowing $O(\log N)$ access to the maximum value (peekMax).
• When popMax() is called, you find the max value in the TreeMap, get the most recently pushed Node from its list, remove that Node from the Doubly-Linked List, and update the TreeMap.

Example explanation

Operations: push(5), push(1), push(5). Stack (Linked List): head -> 5a -> 1 -> 5b -> tail. TreeMap: {1: [1], 5: [5a, 5b]} (sorted by key).

Call popMax():

• The TreeMap says max key is 5.
• We grab the last node added for 5: 5b.
• We remove 5b from the TreeMap list.
• We remove 5b from the Doubly-Linked List. List becomes: head -> 5a -> 1 -> tail. Return 5.

Call pop():

• Removes the tail of the list: 1.
• Update TreeMap to remove 1. List becomes: head -> 5a -> tail. Return 1.

Common mistakes candidates make

A common mistake is using two standard Stacks (one for values, one for maximums) like you would for a "Min Stack". While this works for peekMax(), it utterly fails for popMax(). To pop the maximum from the middle of the stack, you would have to unload and reload the entire stack, causing popMax() to be $O(N)$. The Ordered Set + Linked List guarantees $O(\log N)$ performance.

Interview preparation tip

For the Max Stack coding problem, treat it exactly like the LRU Cache problem. The "Doubly-Linked List with an external lookup dictionary" pattern is identical. The only difference is that instead of a Hash Map indexing keys, you are using a TreeMap/Balanced Tree indexing values to allow for quick maximum extraction. Memorize the Node removal logic for Doubly-Linked Lists.