Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

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

Using a single max heap: Heaps don't support efficient removal of arbitrary elements, making pop() operations O(n) - use a doubly-linked list for O(1) deletion

Forgetting recency for duplicates: When multiple elements have the max value, must track insertion order - store elements with timestamps or in insertion-order collections

Not updating both structures: Every operation must maintain consistency between the stack structure and max-tracking structure - wrap operations in a class to enforce invariants

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.

Solution

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def append(self, val):
        node = Node(val)
        if not self.tail:
            self.head = self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        return node
    
    def remove(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            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.

Solution

import bisect
class TreeMap:
    def __init__(self):
        self.keys = []  # sorted list of unique values
        self.map = {}   # value -> list of Node references
    
    def 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 None
    
    def 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.

Solution

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.tail
        val = node.val
        self.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 val
    
    def top(self):
        return self.dll.tail.val
    
    def peekMax(self):
        return self.tree.get_max()
    
    def popMax(self):
        node = self.tree.pop_max_node()
        val = node.val
        self.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

Overview

Lesson

Stack

This lesson provides foundational understanding of stack data structures, which is essential for implementing the Max Stack problem. Understanding basic stack operations and patterns will help students approach the more complex Max Stack design problem.

Learn

Overview

Lesson

Stack

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.

Learn

Overview

Lesson

Heap

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.

Learn

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early December, 2025

Senior

Early December, 2025

Senior

45 mins questions for Max Stack implementation

Early December, 2025

Mid-level

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 716. Max Stack

DESCRIPTION

Understanding the Problem

Building Intuition

Common Pitfalls

Implementation

Doubly-Linked List for Stack Storage

TreeMap for Maximum Tracking

Complete MaxStack Integration

What We've Learned

Problems to Practice

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact