Get Minimum and Maximum From a Stack in O(1) Time

The moment people hear "minimum" and "maximum", their mind runs towards sorting or looping through the array. But the interviewer has already closed that door — they said O(1). No loops. No sorting. Every operation, including getMin and getMax, must finish in constant time.

This is one of those problems where the answer, once you see it, feels almost like a magic trick. So let us sit together and understand the thinking, step by step.

The Problem

We want a stack that supports the usual operations — push, pop, top — but with two extra powers:

• getMin() → returns the smallest element currently in the stack, in O(1).
• getMax() → returns the largest element currently in the stack, in O(1).

The "currently in the stack" part is what makes it interesting. When we pop elements, the minimum and maximum might change. So we cannot just remember one min and one max and be done — because the moment we pop the minimum element, we need the previous minimum to reappear instantly.

The Naive Thinking (and Why It Fails)

The first idea is: "Let me just keep a single min variable and update it on every push."

This works for push. But think about pop. Suppose our stack is [5, 2, 8] and min = 2. Now we pop 8. Fine, min is still 2. But now we pop 2. What is the new minimum? We would have to scan the remaining elements to find that it is 5. And scanning is O(n). The magic is broken.

So a single variable is not enough. We need a way to remember, at every level of the stack, what the min and max were at that moment. And that history must pop away automatically as we pop elements.

The Core Idea

Here is the beautiful insight:

Instead of storing just the value, let every element also carry the minimum and maximum of the stack at the time it was pushed.

Think of it like this. Each element does not just say "my value is 8." It says "my value is 8, and at the moment I entered, the smallest so far was 2 and the largest was 8." Every element carries its own little snapshot of the min and max below and including itself.

Why is this so powerful? Because:

• When we push, the new min is simply Math.min(newValue, previousTop.min), and the new max is Math.max(newValue, previousTop.max). One comparison each. O(1).
• When we pop, the snapshot goes away with the element automatically. The new top already carries the correct min and max for its level. Nothing to recompute. O(1).
• getMin and getMax just peek at the top element's stored snapshot. O(1).

The history takes care of itself. That is the whole trick.

The Implementation

Let us turn this idea into clean code. Each entry in our stack is a small object holding three things: the value, the min up to here, and the max up to here.

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

    push(x) {
        if (this.stack.length === 0) {
            // first element: it is its own min and max
            this.stack.push({ value: x, min: x, max: x });
        } else {
            let top = this.stack[this.stack.length - 1];
            this.stack.push({
                value: x,
                min: Math.min(x, top.min),
                max: Math.max(x, top.max)
            });
        }
    }

    pop() {
        if (this.stack.length === 0) return -1;
        return this.stack.pop().value;
    }

    top() {
        if (this.stack.length === 0) return -1;
        return this.stack[this.stack.length - 1].value;
    }

    getMin() {
        if (this.stack.length === 0) return -1;
        return this.stack[this.stack.length - 1].min;
    }

    getMax() {
        if (this.stack.length === 0) return -1;
        return this.stack[this.stack.length - 1].max;
    }
}

let s = new MinMaxStack();
s.push(5);
s.push(2);
s.push(8);
console.log(s.getMin());  // 2
console.log(s.getMax());  // 8
s.pop();                  // removes 8
console.log(s.getMax());  // 5  (the old max comes back on its own)

Walking Through the Code

Let us not run away after pasting. Let us feel what each line is doing.

The push, first element:

this.stack.push({ value: x, min: x, max: x });

When the stack is empty, the very first element has no history to compare against, so it is trivially its own minimum and its own maximum. Simple.

The push, every other element:

let top = this.stack[this.stack.length - 1];
this.stack.push({
    value: x,
    min: Math.min(x, top.min),
    max: Math.max(x, top.max)
});

This is the heart of everything. We look at the current top's snapshot, and the new element inherits the better of "the new value" versus "whatever the min/max was below it." Notice we never look further down than one element. Just the top. That is why it is O(1).

The pop:

return this.stack.pop().value;

We simply remove the top and hand back its value. The min/max snapshot leaves along with it — and we do not have to do anything to restore the old min/max, because the element now on top already carries the correct one. This automatic restoration is the elegant part.

getMin and getMax:

They just peek at the top element and read its stored min or max. No looping. Pure O(1).

Let Us Trace It

Take pushes 5, then 2, then 8. Watch what each element stores:

Right now the top is 8, so getMin() reads 2 and getMax() reads 8. Correct.

Now pop() removes 8. The top becomes the 2 element, which stored min = 2, max = 5. Instantly, getMin() gives 2 and getMax() gives 5 — the old maximum came back on its own, without any scanning. That is the beauty we were chasing.

The Trade-Off: Time vs Space

Now, being your well-wisher, let me be honest with you, because a sharp interviewer will definitely ask.

We achieved O(1) time for every operation. Wonderful. But look at the cost — for each element we now store two extra numbers (a min and a max). So the space usage is roughly three times that of a plain stack, still O(n) overall, but heavier.

Is that a problem? Usually not — memory is cheap and predictable, and constant-time queries are often worth it. But you should be able to say this out loud: "I traded some extra space to buy constant-time min and max." That sentence alone shows the interviewer you understand engineering is about trade-offs, not just correctness.

There is also a classic space-optimised variation using a second stack that only pushes a new min when a smaller value arrives. It saves memory in some cases, but the snapshot approach above is the cleanest to explain and the easiest to get right under pressure. For an interview, clarity wins.

Complexity

• Time: push, pop, top, getMin, getMax — all O(1). Every single one.
• Space: O(n), with a constant factor of about 3 because of the stored min and max per element.

Final Thoughts

This problem teaches a lesson that goes far beyond stacks: when you cannot afford to compute something later, carry the answer with you. Instead of hunting for the minimum when asked, each element quietly remembers the minimum from the moment it arrived. The work is spread out, one tiny comparison at a time, so that the answer is always ready and waiting.

Keep this idea close. "Precompute and carry it along" is a pattern you will reach for again and again as the problems get harder.

Happy coding, and all the best for your interviews!