Coding Interview: How Do You Design a Max Stack with popMax?

Problem and context

Implement MaxStack: push(x) adds an item, pop() removes and returns the top, top() reads the top, peekMax() reads the maximum, and popMax() removes and returns the maximum closest to the top. Repeated maxima use a last-in-first-out tie-break; empty-stack behavior must be an explicit error or empty result.

The public LeetCode problem and recent interview-question records use this interface. It differs from a prefix-minimum stack: popMax must locate an interior node and restore the remaining stack order.

What the interviewer is testing

• Whether you fix the duplicate-maximum tie-break and empty-stack contract first.
• Whether you can explain why one currentMax variable cannot restore the next maximum after deletion.
• Whether you separate stack order from value order and remove the same node from both indexes.
• Whether you distinguish an amortized O(1) auxiliary-stack design from an O(log n) ordered-index design.

Clarifications before coding

1. Must popMax be O(1), amortized O(1), or may it be O(log n)? This determines the data structure.
2. For duplicate maxima, must the closest-to-top item be removed, or is any maximum acceptable? The rule changes index lookup.
3. Are stable iterators, concurrent calls, or persistence required? They change node lifetime and locking.
4. Are values comparable objects or bounded integers? Bounded integers allow buckets; generic objects normally need a comparison index.

30-second answer

“I wrap each value in a node with a monotonically increasing sequence number. A doubly linked list preserves stack order; an ordered index sorts by (value, sequence), so its last entry is the maximum closest to the top. top reads the list tail, peekMax reads the index tail, and popMax takes that node and unlinks it through its list pointers. With a balanced-tree index, push, pop, peekMax, and popMax are O(log n), while top is O(1). If only top operations and peekMax need constant time, an auxiliary max stack is simpler, but popMax cannot honestly remain O(1).”

Step-by-step deep dive

Step 1: Separate stack order from sorted order.

Each node stores value, a monotonically increasing sequence, prev, and next. The list tail is the stack top. The ordered key is (value, sequence); for equal values, the larger sequence sorts later, making the index tail the maximum nearest the top.

Step 2: Choose a deletable ordered index.

Use a duplicate-aware balanced tree, a TreeMap plus an ordered node set, or a two-level index from value to ordered sequence IDs. A lone currentMax is insufficient: after deleting it, the next maximum and its node must be found.

Step 3: Keep all five operations synchronized.

• push: create a node, append it to the list, and insert it into the ordered index.
• pop: take the list tail, remove that node from the ordered index, then unlink it.
• top: return the list tail’s value.
• peekMax: return the ordered index tail’s value.
• popMax: take the ordered index tail, unlink it through its list pointers, then remove it from the index.

The pseudocode shows the key invariant; the concrete tree API is language-specific:

node = orderedByValueAndSequence.last()
orderedByValueAndSequence.erase(node.key)
unlink(node.prev, node, node.next)
return node.value

Step 4: Complexity and the simpler alternative.

With a balanced tree, top is O(1) and the other index operations are O(log n); space is O(n). If amortized O(n) popMax is acceptable, a main stack plus a prefix-max stack records the maximum at every depth. That is easier, but it does not fit frequent arbitrary-position removal.

Step 5: Duplicates, empty state, and node identity.

The sequence solves both duplicate ordering and the popMax tie-break. Empty operations return one consistent error. Each node appears exactly once in the list and once in the index; remove the same node from both structures rather than reconstructing it from only its value.

Step 6: Test order and indexes.

Use a slow array as a reference model. Test [5,1,5] with two popMax calls; it should remove the top 5 and then the bottom 5. Cover negatives, all-equal values, empty state, alternating push/pop, an interior maximum, repeated removals, and long random sequences. After every operation, verify list order, index size, and peekMax.

High-quality sample answer

“I would use a doubly linked list for stack order and a balanced ordered index keyed by (value, sequence) for maximum lookup. The sequence is increasing, so the largest sequence among equal maxima is the one closest to the top. Each node carries both list pointers and its index key: pop takes the list tail, popMax takes the index tail, and both remove that same node from the other structure. Top is O(1), the remaining operations are O(log n), and space is O(n). If the interviewer only needs peekMax, I would use an auxiliary max stack to reduce implementation complexity.”

Common mistakes

• Keeping only one current maximum → the next maximum is unknown after deletion → maintain a searchable ordered index.
• Treating popMax as pop → the wrong position is removed and stack order changes → find the node by value index, then unlink by list pointer.
• Leaving duplicates without a sequence → the top-most maximum cannot be proven → key by (value, sequence).
• Removing from the index but not the list → top can return a deleted node → share node identity and update both structures atomically.
• Claiming popMax is O(1) for the auxiliary-stack design → arbitrary removal usually moves items or rebuilds state → state amortized and worst-case bounds precisely.

Follow-up questions and answers

Follow-up 1: Can every operation be O(1)?

For fixed-width integers, bucketed or specialized integer-priority structures are possible, but the bound depends on key width, memory, and the computational model. For arbitrary comparable objects, give the honest O(log n) index solution instead of mixing amortized, expected, and worst-case claims.

Follow-up 2: How would you make it thread-safe?

The simplest contract protects each compound operation with one lock so the list and ordered index cannot temporarily diverge. Higher concurrency may use sharding or immutable snapshots, but popMax removes from two structures atomically and cannot be made consistent by assuming separately acquired locks are enough.

Follow-up 3: What if only peekMax, not popMax, is required?

Use a main stack and an equal-length prefix-max stack. Push records the new maximum in both stacks; pop removes from both; top and peekMax read their respective tops. Every operation is O(1), and duplicate maxima must be recorded repeatedly.