Building a Stack with a getMax() function

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

class MaxStack {
    constructor() {
        this.stack = [];      // Main stack
        this.maxStack = [];   // Stack tracking maximums
    }

    push(value) {
        this.stack.push(value);

        // Push new max or current max to maxStack
        if (this.maxStack.length === 0 || value >= this.getMax()) {
            this.maxStack.push(value);
        } else {
            this.maxStack.push(this.getMax());
        }
    }

    pop() {
        if (this.stack.length === 0) {
            throw new Error("Stack is empty");
        }

        this.maxStack.pop();
        return this.stack.pop();
    }

    getMax() {
        if (this.maxStack.length === 0) {
            throw new Error("Stack is empty");
        }
        return this.maxStack[this.maxStack.length - 1];
    }

    peek() {
        if (this.stack.length === 0) {
            throw new Error("Stack is empty");
        }
        return this.stack[this.stack.length - 1];
    }
}

// Example usage:
const stack = new MaxStack();
stack.push(5);
console.log(stack.getMax());  // 5
stack.push(3);
console.log(stack.getMax());  // 5
stack.push(7);
console.log(stack.getMax());  // 7
stack.pop();
console.log(stack.getMax());  // 5

class MaxStack {
    constructor() {
        this.stack = [];
        this.maxStack = [];
    }

    push(value) {
        this.stack.push(value);

        // Only push to maxStack if new max or first element
        if (this.maxStack.length === 0 || value >= this.getMax()) {
            this.maxStack.push(value);
        }
    }

    pop() {
        if (this.stack.length === 0) {
            throw new Error("Stack is empty");
        }

        const value = this.stack.pop();

        // Remove from maxStack only if it was the max
        if (value === this.getMax()) {
            this.maxStack.pop();
        }

        return value;
    }

    getMax() {
        if (this.maxStack.length === 0) {
            throw new Error("Stack is empty");
        }
        return this.maxStack[this.maxStack.length - 1];
    }
}