# Building a Stack with a getMax() function

Source: https://www.techinterview.org/post/3233459129/building-a-stack-with-a-getmax-function/
Updated: 2026-04-16 · techinterview.org

Suppose you had a Stack class. Write a new class MaxStack which, in addition to push() and pop(), has a method getMax() which returns the largest item in the stack. Use your existing Stack class to store the stack’s contents.

Don’t just use pop() to “dig” through your stack to find the max—do something that lets you return the max in constant time.

Solution

We could have an instance variable where we hold the max, but there’s a problem—when we pop that item from our stack it’s no longer the max. Now we have to “dig” through our stack to find the new max. Ideally we’d keep track of the current max as well as what the new max will be when that max is popped.

The trick is to have two instances of Stack inside our MaxStack. One holds the actual stack contents, while the other (call it maxesStack) holds the maxes. Whenever we push() an item, if it’s larger than the top item in maxesStack, we also push it to maxesStack. Whenever we pop() an item, if it’s the same as the top item in maxesStack(), we also pop() it from maxesStack.

So at any given point we can get the overall max in constant time be peeking at the top item in maxesStack.

## 2026 Update: Stack with O(1) Max — Two Approaches

Design a stack that supports `push()`, `pop()`, and `getMax()` all in O(1) time and O(n) space. This is one of the most frequently asked stack design problems at FAANG.


```
class MaxStack:
    """Approach 1: Auxiliary stack tracks running max."""

    def __init__(self):
        self.stack = []
        self.max_stack = []  # Each entry: current max at that depth

    def push(self, val: int) -> None:
        self.stack.append(val)
        current_max = max(val, self.max_stack[-1] if self.max_stack else val)
        self.max_stack.append(current_max)

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.max_stack.pop()
        return self.stack.pop()

    def get_max(self) -> int:
        if not self.max_stack:
            raise IndexError("empty stack")
        return self.max_stack[-1]

    def peek(self) -> int:
        return self.stack[-1]


class MaxStackSpaceOptimized:
    """
    Approach 2: Store (value, max) pairs — same O(n) space but simpler.
    Trade-off: uses more memory per element but eliminates a separate list.
    """

    def __init__(self):
        self.stack = []  # Each element: (value, max_so_far)

    def push(self, val: int) -> None:
        current_max = max(val, self.stack[-1][1] if self.stack else val)
        self.stack.append((val, current_max))

    def pop(self) -> int:
        return self.stack.pop()[0]

    def get_max(self) -> int:
        return self.stack[-1][1]


# Test
s = MaxStack()
for val in [3, 1, 5, 2, 4]:
    s.push(val)
    print(f"push({val}), max={s.get_max()}")
# push(3), max=3
# push(1), max=3
# push(5), max=5
# push(2), max=5
# push(4), max=5

s.pop()
s.pop()
print(f"after 2 pops, max={s.get_max()}")  # max=5 (5 is still there)
s.pop()
print(f"after 3 pops, max={s.get_max()}")  # max=3 (5 is gone)
```

**Follow-up variations asked at FAANG 2025-2026:**

- **Min stack:** Same approach, track minimum instead (LeetCode #155)

- **Queue with max:** Harder — use a monotonic deque (LeetCode #239 Sliding Window Maximum)

- **Concurrent max stack:** Add a lock per operation or use lock-free CAS operations

- **Persistent max stack:** Use a persistent/functional approach where pop() doesn't destroy history