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.

💡Strategies for Solving This Problem

Approach 1: Track Maximum with Each Element

The key insight is to store not just the element, but also the maximum value at each level of the stack. This way, we always know what the maximum is in O(1) time.

Key Considerations:

Space vs. Time Trade-off: We use extra space to store the max at each level, but gain O(1) getMax() operation
Update Strategy: When pushing, compare the new element with the current max
Pop Considerations: The max is automatically maintained since we stored it at each level

Approach 2: Separate Max Stack

Maintain two stacks: one for regular elements and another that only tracks maximum values. This can be more space-efficient if many elements have the same maximum.

Time Complexity:

All operations (push, pop, getMax) run in O(1) time with either approach.

✅Solution

Solution Using Auxiliary Stack

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

Space-Optimized Solution

If we want to optimize space when many elements share the same maximum:

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];
    }
}

Complexity Analysis:

Time Complexity: O(1) for all operations (push, pop, getMax)
Space Complexity: O(n) where n is the number of elements in the stack