Max Stack - Solution & Explanation

Problem Overview: Design a stack that behaves like a normal stack but also supports two extra operations: peekMax() to view the maximum element and popMax() to remove the maximum element. If multiple elements share the maximum value, remove the one closest to the top. The challenge is maintaining both stack order and fast access to the current maximum.

Approach 1: Simple Stack Scan (O(n) popMax)

Use a regular stack to store values. push, pop, and top work in O(1) time. For peekMax(), scan the stack to find the maximum element in O(n) time. For popMax(), repeatedly pop elements into a temporary stack until the maximum is found, remove it, then restore the remaining elements. Time complexity becomes O(n) for both max operations with O(n) auxiliary space during the operation.

Approach 2: Two Stacks (O(n) popMax)

Maintain two stacks: the main stack and a max-tracking stack that stores the maximum value at each level. Each push updates the max stack with max(current, previousMax). peekMax() becomes O(1). However, removing the maximum still requires popping elements until the max appears, then pushing them back. That makes popMax() O(n) time and O(n) temporary space. This improves read performance but not deletion of arbitrary maximum elements.

Approach 3: Doubly Linked List + Ordered Map (O(log n))

The optimal design combines a doubly linked list with an ordered map (like TreeMap or balanced BST). The doubly linked list maintains stack order, enabling push, pop, and top in O(1). The ordered map stores values as keys and a list of node references as values. This lets you locate the largest key quickly.

When pushing, insert a node at the tail of the linked list and store its reference in the ordered map. For peekMax(), retrieve the largest key in the map in O(log n) or O(1) depending on implementation. For popMax(), find the largest value, remove the most recently inserted node from its node list, and unlink that node from the doubly linked list. Both structures stay synchronized.

This design efficiently supports all operations: linked list handles stack order while the ordered structure provides fast maximum lookup. Time complexity is O(log n) for push and popMax(), and O(1) for standard stack operations. Space complexity is O(n). It demonstrates how combining a linked list with an ordered set solves conflicting access patterns.

Recommended for interviews: The doubly linked list + ordered map approach is what interviewers typically expect for this hard design problem. Showing the brute-force stack scan first demonstrates understanding of the constraints, while transitioning to the balanced-map design shows strong data structure design skills.