HardLinked ListStackDesignDoubly-Linked ListOrdered SetUpdated Sep 2026

716. Max Stack

Asked at Walmart, LinkedIn

Difficulty

Hard

Time

O(1) for top, O(log n) for push,

Space

O(n)

Pattern

Linked List

Companies

2

Problem

Design a class MaxStack that behaves like a normal stack but can also tell you the largest value inside it. It must support these five operations:

  • push(x): put x on top of the stack.
  • pop(): remove the top element and return its value.
  • top(): return the top element's value without removing it.
  • peekMax(): return the largest value in the stack without removing it.
  • popMax(): remove the top-most occurrence of the largest value and return that value.

The tricky part is popMax(). The maximum value may appear many times, and you must remove the one closest to the top. Removing an element from the middle of a stack is not natural, so you need extra bookkeeping. The required speed is O(1) for top() and O(log n) for every other call, where n is the number of elements currently in the stack.

A stack that also knows its maximum

stack (bottom → top)515nulltopTwo 5s are present; the max is 5 and the top-most 5 isthe one at the top.after popMax()51nulltoppopMax removed the top 5, so the stack shrinks to [5,1] and the top is now 1.
Values sit in insertion order, and popMax must pull out the top-most copy of the largest value.

Constraints

  • ●-10^7 <= x <= 10^7
  • ●At most 10^5 calls will be made in total to push, pop, top, peekMax and popMax.
  • ●pop, top, peekMax and popMax are only called when the stack is non-empty.

Examples

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]
WhyAfter pushing 5, 1, 5 the stack is [5, 1, 5] from bottom to top. top() gives 5. popMax() removes the top-most 5 (the one at the top), leaving [5, 1]. top() now gives 1, and peekMax() still gives 5. pop() removes 1, leaving [5], and the final top() gives 5.
Example 2
Input["MaxStack", "push", "push", "push", "push", "popMax", "pop", "pop", "pop"] [[], [5], [1], [5], [3], [], [], [], []]
Output[null, null, null, null, null, 5, 3, 1, 5]
WhyThe stack is [5, 1, 5, 3] from bottom to top. popMax() removes the top-most 5 (the second element), leaving [5, 1, 3]. Then pop() returns 3, pop() returns 1, and pop() returns the remaining 5.

Asked At

2 companies
CompanyDifficulty
WalmartHardView all Walmart questions →
LinkedInHardView all LinkedIn questions →

How to Think About It

1

Naive approach: use a single stack. popMax requires scanning the entire stack — O(n) for popMax.

2

Use two stacks: one for normal operations and a second stack tracking the maximum at each level.

3

For O(1) popMax, use a doubly linked list to maintain insertion order and a balanced BST (or sorted map) for O(1) access to max.

4

Alternatively, use a single doubly linked list where each node has a value, plus a HashMap from value to a sorted set of nodes. Push appends to the list and adds to the map.

5

popMax looks up the max key in the map, removes the last node with that value from the sorted set, removes it from the linked list, and returns the value.

Optimal Approach

Use a doubly linked list to store elements in insertion order, and a TreeMap (balanced BST) mapping each value to a SortedSet of list nodes with that value. Push appends a node to the list and inserts it into the map. Top returns the tail of the list. PeekMax returns the last key in the TreeMap. Pop removes the tail of the list and its entry from the map. PopMax retrieves the largest key, removes the last node in its set, and removes that node from the list. All operations are O(1) amortized.

Linked list plus an ordered map

list515nulltailpush(5), push(1), push(5) appends nodes at the tail.map: value → nodes (top-most last)valuenodes1n25n1, n3The largest key is 5, and its last node n3 is thetop-most 5.after popMax()51nulltailRemove n3 from the list and from the set for value 5;the map now holds only {1: n2, 5: n1}.top = tail.prevpeekMax = largest key in mappopMax = last node of largest key
The list keeps order; the map keyed by value gives O(log n) access to the max and to the top-most node with that value.
ComplexityTime O(1) for top, O(log n) for push,Space O(n)Each element lives in one linked-list node and one entry in the ordered map, so memory grows linearly with the number of elements.

What Trips People Up in Real Interviews

1

Ask whether duplicate maximum values are possible (yes). Clarify that popMax removes one occurrence.

2

Discuss the tradeoff between simplicity (two stacks, O(n) popMax) and optimality (doubly linked list + sorted map, O(1) all ops).

3

If using the linked list approach, clearly define the data structures: a doubly linked list for order, a TreeMap/SortedDict for values.

4

Walk through push, pop, popMax with an example to verify correctness.

5

Mention that in practice, the two-stack approach is often sufficient and easier to implement.

Solution Code

O(1) for top, O(log n) for push, time
class Node:
    def __init__(self, val=0, prev=None, nxt=None):
        self.val = val
        self.prev = prev
        self.nxt = nxt

class MaxStack:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.nxt = self.tail
        self.tail.prev = self.head
        self.nodes = {}
        self.sorted_vals = {}

    def push(self, x):
        node = Node(x, self.tail.prev, self.tail)
        self.tail.prev.nxt = node
        self.tail.prev = node
        self.nodes[id(node)] = node
        if x not in self.sorted_vals:
            self.sorted_vals[x] = set()
        self.sorted_vals[x].add(id(node))

    def pop(self):
        node = self.tail.prev
        val = node.val
        self.tail.prev = node.prev
        node.prev.nxt = self.tail
        del self.nodes[id(node)]
        self.sorted_vals[val].discard(id(node))
        if not self.sorted_vals[val]:
            del self.sorted_vals[val]
        return val

    def top(self):
        return self.tail.prev.val

    def peekMax(self):
        return max(self.sorted_vals.keys())

    def popMax(self):
        val = max(self.sorted_vals.keys())
        node_id = self.sorted_vals[val].pop()
        if not self.sorted_vals[val]:
            del self.sorted_vals[val]
        node = self.nodes[node_id]
        node.prev.nxt = node.nxt
        node.nxt.prev = node.prev
        del self.nodes[node_id]
        return val

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Max Stack problem?

Design a stack that supports push, pop, top, peekMax, and popMax operations. Implement the MaxStack class with O(1) time complexity for all operations. The popMax operation removes and returns the maximum element from the stack.

How do you solve Max Stack?

The optimal approach runs in O(1) for top, O(log n) for push, time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Max Stack?

Max Stack is asked at Walmart, LinkedIn. It is a hard difficulty problem.

What are common mistakes on Max Stack?
  • Ask whether duplicate maximum values are possible (yes). Clarify that popMax removes one occurrence.
  • Discuss the tradeoff between simplicity (two stacks, O(n) popMax) and optimality (doubly linked list + sorted map, O(1) all ops).
  • If using the linked list approach, clearly define the data structures: a doubly linked list for order, a TreeMap/SortedDict for values.
  • Walk through push, pop, popMax with an example to verify correctness.
  • Mention that in practice, the two-stack approach is often sufficient and easier to implement.