716. Max Stack — DSA Atlas

716

HardData Structure DesignHeap with lazy deletion and unique sequence idsStack plus lazy-deletion max-heap keyed by recency

Max Stack

Design a stack supporting push, pop (remove/return the top), top (peek the top), peekMax (return the maximum element), and popMax (remove and return the maximum element). When several elements share the maximum value, popMax must remove the one closest to the top.

Open official problem prompt ↗

In plain English

Serve two orderings of the same elements at once: last-in-first-out for top/pop and largest-first (most recent on ties) for peekMax/popMax.

Picture it like this

Two librarians share one collection: one shelves books by arrival time, the other by height. When either lends a book out, they leave a sticky note (the removed set) so the other librarian knows to skip that copy when they next reach for it.

Example

Input: MaxStack(); push(5); push(1); push(5); top(); popMax(); top(); peekMax(); pop(); top()
Output: [null, null, null, null, 5, 5, 1, 5, 1, 5]
Why: Stack is [5,1,5]; top is 5; popMax removes the topmost 5 leaving [5,1]; top is 1; peekMax is 5; pop removes 1 leaving [5]; top is 5.

Constraints

-10^7 <= x <= 10^7At most 10^5 calls to push, pop, top, peekMax, and popMaxpop, top, peekMax, popMax are only called on a non-empty stack

Pattern lesson

See the pattern, then code

Stack plus lazy-deletion max-heap keyed by recency

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Tag every push with an increasing sequence id. Keep a stack for LIFO order and a max-heap ordered by (value, id) for max order. Deletions in one structure are recorded in a 'removed' set and applied lazily when the other structure surfaces the same id.

New words, made simpleKnow these before the algorithm

Lazy deletion: Mark an element removed instead of physically deleting it everywhere; skip it when it later surfaces.
Sequence id: A monotonically increasing tag giving every push a unique, recency-ordered key.
Tie-break by recency: Among equal values, the most recently pushed (largest id) is treated as the maximum.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Single stack, scan for max

Linear max operations are too slow at 10^5 calls.

Keep only a stack; scan it to find and remove the max on popMax.

Time O(n) per peekMax/popMaxSpace O(n)

Best choiceStack + max-heap with lazy deletion

Both views stay logarithmic; the removed set keeps them consistent.

Mirror pushes into a heap keyed by (value, id); reconcile via a removed set.

Time O(log n) amortizedSpace O(n)

The rule we keep true

Invariant

An element is logically present exactly when its id is NOT in the removed set; both the stack top and the heap root are cleaned to a live element before any read.

Why this is correct

Reasoning

Every element has one unique id shared by both structures. Removing it in either view records the id once; the cleaning loops guarantee neither view ever returns a stale element, so the two orderings agree on which elements are live. Each id is pushed to and popped from each structure at most once, giving amortized O(log n).

The algorithm in three movesSay these aloud before coding

1On push, append (id, value) to the stack and push (-value, -id) to the heap; increment id

stack=[(0,5),(1,1),(2,5)] heap top=(-5,-2)

2For top/pop, discard stack entries whose id is in the removed set, then read or pop

popMax -> remove id 2, return 5

3For peekMax/popMax, discard heap entries whose id is removed, then read or pop

top skips id 2 -> returns 1

4Whenever you remove an element in one view, add its id to the removed set so the other view skips it

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read5, 1, 5

2 · AskWhat are the ids?

3 · Update statestack=[(0,5),(1,1),(2,5)], heap has (-5,-2),(-5,-0),(-1,-1)

4 · Resultid 2 is the most recent 5

Key takeaway

The topmost 5 (id 2) is the heap's minimum tuple (-5,-2), so popMax removes it rather than the older 5 (id 0).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-7Two mirrors and a tombstone set
stack gives LIFO order, heap gives max order, removed marks logically deleted ids, seq issues unique ids.
2
Lines 9-12push
Record the same (id, value) in both structures using negation so heapq acts as a max-heap.
3
Lines 14-20Cleaning loops
Before any read, discard tombstoned entries so the exposed element is guaranteed live.
4
Lines 34-39popMax
Pop the heap root (largest value, largest id on ties) and tombstone its id so the stack skips it later.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Duplicate maximum values where popMax must take the most recent one
Interleaving pop and popMax so tombstones pile up in both views
A single element pushed then popped via popMax then the stack must read empty-safe (only called non-empty per constraints)
Negative values (x can be as low as -10^7)

Common beginner mistakes

Breaking value ties by lowest id instead of highest, removing an older duplicate than required
Forgetting to clean the OTHER structure, so a tombstoned element resurfaces
Storing raw value in the heap without an id, making recency tie-breaking impossible
Not negating both value and id, which flips tie ordering

Check your understanding

Why must the heap key be (value, id) rather than just value?

PyPython 3 · solution.py

Optimal

1import heapq23class MaxStack:4    def __init__(self):5        self.stack = []6        self.heap = []7        self.removed = set()8        self.seq = 0910    def push(self, x: int) -> None:11        self.stack.append((self.seq, x))12        heapq.heappush(self.heap, (-x, -self.seq))13        self.seq += 11415    def _clean_stack(self) -> None:16        while self.stack and self.stack[-1][0] in self.removed:17            self.stack.pop()1819    def _clean_heap(self) -> None:20        while self.heap and -self.heap[0][1] in self.removed:21            heapq.heappop(self.heap)2223    def pop(self) -> int:24        self._clean_stack()25        sid, val = self.stack.pop()26        self.removed.add(sid)27        return val2829    def top(self) -> int:30        self._clean_stack()31        return self.stack[-1][1]3233    def peekMax(self) -> int:34        self._clean_heap()35        return -self.heap[0][0]3637    def popMax(self) -> int:38        self._clean_heap()39        neg_val, neg_id = heapq.heappop(self.heap)40        self.removed.add(-neg_id)41        return -neg_val

Time complexityO(log n) amortized per operationOptimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleAmazonLinkedIn

Max Stack

Max Stack

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design