Max Stack

Table of Contents +

This is a design question, not a single puzzle. You have to build a stack that also remembers its biggest value at all times. So the interviewer is checking if you can keep two things in sync as the data changes. The clean trick is to use a second stack that tracks the maximum. So you keep both answers ready without scanning.

🎯 The Problem

You have to design a special stack that also keeps its biggest value ready at all times.

push adds a value on top.
pop removes and returns the top value.
top looks at the top value without removing it.
peekMax returns the biggest value in the stack without removing it.
popMax removes and returns the biggest value. If that value appears more than once, it removes only the topmost copy.

Operations and results:
push(5)    -> stack bottom..top: [5]
push(1)    -> [5, 1]
push(5)    -> [5, 1, 5]
top()      -> 5      (the top value)
popMax()   -> 5      (removes the topmost biggest, now [5, 1])
top()      -> 1
peekMax()  -> 5      (biggest still in the stack)
pop()      -> 1      (now [5])
top()      -> 5

Here is the idea. We keep two stacks side by side. One holds the values. The other holds the running maximum at each level.

🐢 Approach 1: One Stack, Scan for the Max (Brute Force)

Keep a single stack of values and scan it whenever you need the biggest.

The idea:

Use one plain stack of values.
push, pop and top work the normal way.
For peekMax, scan the whole stack and find the biggest value.
For popMax, scan to find the biggest, then remove that one item.

Why it is weak:

Every peekMax and popMax walks the entire stack.
So each of those calls is O(n), where n is the number of items.
A fast maximum is impossible with this design.

Here is the scan-for-max code:

class MaxStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def pop(self):
        return self.stack.pop()

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

    def peekMax(self):
        return max(self.stack)

    def popMax(self):
        value = max(self.stack)
        self.stack.pop(len(self.stack) - 1 - self.stack[::-1].index(value))
        return value

⚡ Approach 2: Two Stacks Moving Together (Best)

The idea in one line: keep a second stack that always holds the running maximum, so the biggest value is ready without scanning.

The idea:

The main stack holds the actual values.
The max stack holds the biggest value seen from the bottom up to that same level.
Both stacks always have the same height.

How it works:

On push, add the value to the main stack. Then push the larger of the value and the current max-stack top onto the max stack.
The max-stack top is now the biggest value in the whole stack. So peekMax just reads it.
On pop, remove the top of both stacks together. top reads the main-stack top.
On popMax, the biggest value may sit deep. Pop items into a buffer until you reach it, remove it, then push the buffer back. Each push rebuilds the max stack as it goes.

Why it is fast:

push, pop, top and peekMax are all O(1), which means constant time, no scanning.
Only popMax may touch up to n items, so it stays O(n).

Here is the two stacks changing through the operation log. Watch how the max stack top always shows the current biggest value.

Steps to Solve

Keep a main stack for values and a max stack for the running maximum.
For push, add the value to the main stack and add max of value and current max-top to the max stack.
For pop, remove the top of both stacks together and return the main value.
For top, return the top of the main stack.
For peekMax, return the top of the max stack.
For popMax, move items from the main stack into a buffer until you reach the maximum, remove it, then push the buffer back one by one.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses two lists as the stacks and a buffer list inside popMax.

class MaxStack:
    def __init__(self):
        self.main = []  # values
        self.maxes = []  # running maximum

    def push(self, x):
        self.main.append(x)
        cur_max = x if not self.maxes else max(x, self.maxes[-1])
        self.maxes.append(cur_max)  # biggest up to this level

    def pop(self):
        self.maxes.pop()
        return self.main.pop()  # shrink both together

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

    def peek_max(self):
        return self.maxes[-1]  # ready instantly

    def pop_max(self):
        m = self.maxes[-1]
        buffer = []
        while self.main[-1] != m:        # pop until we reach the max
            buffer.append(self.pop())
        self.pop()                       # remove the topmost maximum
        while buffer:
            self.push(buffer.pop())      # push the rest back
        return m


s = MaxStack()
s.push(5)
s.push(1)
s.push(5)
print("top    ->", s.top())
print("popMax ->", s.pop_max())
print("top    ->", s.top())
print("peekMax->", s.peek_max())
print("pop    ->", s.pop())
print("top    ->", s.top())

The output of the above code will be:

top    -> 5
popMax -> 5
top    -> 1
peekMax-> 5
pop    -> 1
top    -> 5

Let us read the Python version line by line so the two-stack design is clear.

self.main = [] is the stack of real values. self.maxes = [] is the stack of running maximums. They always have the same height.

In push, self.main.append(x) adds the value. Then cur_max = x if not self.maxes else max(x, self.maxes[-1]) picks the bigger of the new value and the old maximum. self.maxes.append(cur_max) stores it. So the top of maxes is always the biggest value in the whole stack right now.

In pop, self.maxes.pop() and self.main.pop() remove the top of both. They move together, so they stay the same height.

top returns self.main[-1], the top value. peek_max returns self.maxes[-1], the current biggest, with no scan at all.

In pop_max, m = self.maxes[-1] reads the biggest value. while self.main[-1] != m: pops items into buffer until the top of the main stack is that biggest value. We call self.pop() so both stacks shrink in step. self.pop() after the loop removes that topmost maximum itself.

while buffer: self.push(buffer.pop()) pushes the saved items back in their original order. Each push rebuilds the max stack correctly, because push recomputes the running maximum. return m gives back the value we removed.

⏱️ Time and Space Complexity

With a single stack, peekMax and popMax scan everything, so each is O(n). With two stacks, push, pop, top and peekMax are all O(1), which means constant time. Only popMax may touch up to n items, so it is O(n). Both designs use O(n) memory, but the two-stack design pays a little extra to keep the maximum always ready.

Operation	Single Stack	Two Stacks
push / pop / top	O(1)	O(1)
peekMax	O(n)	O(1)
popMax	O(n)	O(n)

Tip

The two-stack design wins because peekMax becomes instant. popMax is still O(n) because the biggest value can sit deep inside, but a faster popMax needs heavier tools like a balanced tree plus a doubly linked list.

🧩 Key Takeaways

✅ Keep a main stack for values and a max stack for the running maximum.
✅ On push, store the larger of the new value and the old maximum, so peekMax is instant.
✅ Pop both stacks together so they always stay the same height.
✅ For popMax, move items to a buffer until you reach the maximum, remove it, then push the buffer back.
✅ popMax removes only the topmost copy when the maximum value appears more than once.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Largest Rectangle in Histogram
Asteroid Collision

Previous Basic Calculator II Next Maximum Depth of a Binary Tree

Max Stack

Follow Us

Follow Us