Skip to content

716. Max Stack

On LeetCode ->

Problem

Design a stack supporting push, pop, top, peekMax, and popMax. Remove the top-most maximum when maxima repeat.

Require \(O(1)\) for top and \(O(\log n)\) or better for every other operation. Reads and removals are called only on nonempty stacks.

Operation     Return    Stack (bottom → top)
push(5)       None      [5]
push(1)       None      [5, 1]
push(5)       None      [5, 1, 5]
popMax()      5         [5, 1]
top()         1         [5, 1]
peekMax()     5         [5, 1]

class MaxStack:
    def __init__(self):
        pass

    def push(self, x: int):
        pass

    def pop(self):
        pass

    def top(self):
        pass

    def peekMax(self):
        pass

    def popMax(self):
        pass

Key trick

Share nodes between a doubly linked list for stack order and an indexed max heap for maximum order; prioritize nodes by (value, push_id) to resolve ties.

Trap

  • Binary search takes \(O(\log n)\), but insertion into a Python list takes \(O(n)\).
  • A normal heap cannot efficiently remove an arbitrary stack node without tracking its heap index.
  • Lazy deletion gives amortized bounds, but a single cleanup can exceed \(O(\log n)\); it can also make top nonconstant.

Why is it interesting?

It combines two orderings of the same elements, requiring efficient deletion from both whenever either ordering selects a node.

Python solution

class MaxStack:
    class _Node:
        def __init__(self, x: int, push_id: int):
            self.key = (x, push_id)
            self.prev = None
            self.next = None
            self.idx = -1 # index of node in the heap

    def __init__(self):
        # A circular sentinel makes insertion and deletion uniform.
        self.root = self._Node(0, -1)
        self.root.prev = self.root.next = self.root
        self.heap = [] # heap with nodes comparison done with `.key` tuple
        self.next_push_id = 0 # Unique increasing number for breaking heap's ties

    def push(self, x: int) -> None:
        node = self._Node(x, self.next_push_id)
        self.next_push_id += 1

        # Append immediately before the sentinel: this is the stack top.
        tail = self.root.prev
        node.prev, node.next = tail, self.root
        tail.next = self.root.prev = node

        node.idx = len(self.heap)
        self.heap.append(node)
        self._up(node.idx)

    def pop(self) -> int:
        return self._remove(self.root.prev)

    def top(self) -> int:
        return self.root.prev.key[0]

    def peekMax(self) -> int:
        return self.heap[0].key[0]

    def popMax(self) -> int:
        return self._remove(self.heap[0])

    def _swap(self, i: int, j: int) -> None:
        heap = self.heap
        heap[i], heap[j] = heap[j], heap[i]
        heap[i].idx, heap[j].idx = i, j

    def _up(self, i: int) -> None:
        heap = self.heap
        while i:
            j = (i - 1) // 2
            if heap[j].key >= heap[i].key:
                break
            self._swap(i, j)
            i = j

    def _down(self, i: int) -> None:
        heap = self.heap
        n = len(heap)
        while 2 * i + 1 < n:
            j = 2 * i + 1
            if j + 1 < n and heap[j + 1].key > heap[j].key:
                j += 1
            if heap[i].key >= heap[j].key:
                break
            self._swap(i, j)
            i = j

    def _remove(self, node: "_Node") -> int:
        # Unlink the selected node from stack order.
        node.prev.next = node.next
        node.next.prev = node.prev

        # Fill its heap position with the final node, then restore order.
        i = node.idx
        last = self.heap.pop()
        if i < len(self.heap):
            self.heap[i] = last
            last.idx = i
            if i and last.key > self.heap[(i - 1) // 2].key:
                self._up(i)
            else:
                self._down(i)

        return node.key[0]

Time: top and peekMax are \(O(1)\); push, pop, and popMax perform \(O(\log n)\) heap work. Python list resizing is amortized.

Space: \(O(n)\) for \(n\) live elements.

Comment on my solution

Your reasoning correctly identifies duplicate maxima and arbitrary heap deletion as the central difficulties.

  • bisect_left finds an insertion position in \(O(\log n)\), but ordered.insert still costs \(O(n)\).
  • bisect_left(self.stack, max_val) is invalid because stack order is not sorted.
  • self.ordered[max_val] uses an undefined variable; the maximum is self.ordered[-1].
  • Even after fixing those issues, finding and deleting the top-most maximum from a list costs \(O(n)\); shared nodes and heap indices eliminate that scan.
# Ideas:
# - It looks like MinStack problem but is different because here
#   we also have a popMax methode which remove the max element
#   from the stack, not only a pop removing the last pushed element.
# - the O(logn) requirement suggests there's maybe
#   - a binary search,
#   - or a divide-and-conquert strategy
#   - a heap
# - the max can be duplicated
# - problem with using a max heap:
#   - when we pop an element, how to remove it from the heap
# - binary search for insertion of new pushed value keeps an array
#   sorted in O(logn) per operation if I'm not wrong
#   - and we can always find the max
#   - yes but removing it in the stack is O(n)
# - I don't see how to solve this problem

import bisect

class MaxStack:
    def __init__(self):
        self.stack = [] # values
        self.ordered = [] # values ordered
    def push(self, x: int):
        self.stack.append(x)
        idx = bisect.bisect_left(self.ordered, x)
        self.ordered.insert(idx, x)

    def pop(self):
        # ...

    def top(self):
        return self.stack[-1]

    def peekMax(self):
        return self.ordered[-1]

    def popMax(self):
        max_val = self.ordered[max_val]
        idx = bisect.bisect_left(self.stack, max_val)
        # ...

Extra

Problem description

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

  • MaxStack() Initializes the stack object.
  • void push(int x) Pushes element x onto the stack.
  • int pop() Removes the element on top of the stack and returns it.
  • int top() Gets the element on the top of the stack without removing it.
  • int peekMax() Retrieves the maximum element in the stack without removing it.
  • int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

Constraints:

  • -10^7 <= x <= 10^7
  • At most 10^5 calls will be made to push, pop, top, peekMax, and popMax.
  • There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Complement on the insertion number and nodes' heap indices

I think I understand the pattern used but the implementation is not clear to me yet.

  • It seems that nodes in the doubly linked list never change position. They only are removed once which is easy because of prev and next pointers.
  • Node reordering only happens in the heap to keep its max invariant.
  • What is not clear to me is the self.seq incrementation (it's seems to be a total ordering that also include past node that have been removed). What am I missing?
  • I kind a see self.idx set in push operation, but why/how it is updated in _swap operation and what is its link with self.seq? What am I missing?

Your first two observations are correct: surviving nodes keep their relative order in the linked list; only their positions in the heap change.

The missing distinction is that seq records history, whereas idx records current location. They have no numerical relationship.

seq: which equal-valued node wins?

Each push gets a unique, increasing insertion number. A node keeps that number forever.

The heap compares (value, seq) lexicographically:

  • Larger value wins.
  • For equal values, larger seq wins: that node was pushed later.
Push order:    5₀, 1₁, 5₂, 2₃
Stack:        [5₀, 1₁, 5₂, 2₃]
Maximum:       5₂ wins over 5₀

The subscripts represent seq. Among equal values, the most recently pushed surviving node is also the top-most one, because surviving nodes never change their relative stack order.

Removed nodes do not participate in comparisons anymore. Gaps in the sequence numbers are harmless; the counter just ensures every new node is newer than all existing nodes.

idx: where is this node in the heap right now?

Every live node maintains this invariant:

self.heap[node.idx] is node

This lets pop() find the top node's heap position immediately, without searching the heap.

When _swap(i, j) exchanges two heap entries, their stored indices must change too:

Before swap:
heap position    node    node.idx
0                A       0
2                B       2

After swap:
heap position    node    node.idx
0                B       0
2                A       2

That is exactly what these lines do:

heap[i], heap[j] = heap[j], heap[i]

# heap[i] now contains the node that moved to i.
# heap[j] now contains the node that moved to j.
heap[i].idx, heap[j].idx = i, j

The nodes' seq, values, and linked-list pointers remain unchanged.

How they work together

  • seq helps determine which node belongs above another in the heap.
  • idx tells us where a particular node currently sits in the heap.
  • prev and next tell us where that same node sits in stack order.

Both structures reference the same node objects, not copies. Updating a node's idx through the heap is therefore visible when that node is later accessed through the linked list.

Why using the name seq for the insertion number

I don't like the name seq. Why did you choose it? Can you think about other short descriptive variable name for it?

class MaxStack:
    class _Node:
        def __init__(self, x: int, seq: int):
            # ...
    def __init__(self):
        self.root = self._Node(0, -1)
        self.root.prev = self.root.next = self.root
        self.heap = []
        self.seq = 0

    def push(self, x: int) -> None:
        node = self._Node(x, self.seq)
        self.seq += 1
        # ...
    # ...

I chose seq as shorthand for sequence number: a number assigned to each push to record insertion order. It is conventional, but not very explicit.

Alternatives:

  • push_id: identifies the push that created the node; my preference here.
  • order: emphasizes insertion order, though it could be confused with heap order.
  • stamp: suggests a logical timestamp, not actual clock time.

I would name the counter next_id and the node’s assigned number push_id:

node = _Node(x, self.next_id)
self.next_id += 1

# Inside _Node.__init__(self, x, push_id):
self.key = (x, push_id)

This distinguishes the counter’s role from the fixed identifier stored in each node.