Min Stack

1. Problem & Core Objective

The problem

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time.

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   // -3
minStack.pop();
minStack.top();      // 0
minStack.getMin();   // -2   ← the previous minimum is restored

Constraints:

• -2^31 <= val <= 2^31 - 1
• pop, top and getMin are always called on a non-empty stack
• At most 3 * 10^4 calls in total

What the interviewer is actually testing

This is a design question. There's no algorithm to discover — the test is whether you can augment a data structure to answer a new query in O(1).

1. Do you see that the minimum must be stored, not computed? Scanning for it is O(n), which the problem explicitly forbids.
2. Do you realize pop must restore the previous minimum? That's the real difficulty. Tracking a single min field works for push and breaks completely on pop.
3. Can you handle duplicate minima? The two-stack variant has a genuine off-by-one here — using < instead of <= silently corrupts the state.
4. Do you notice the value range? val spans the full int range, which makes the "store differences" optimization overflow unless you widen to long.

2. First-Principles Thought Process

Step 1 — Why the naive fix fails

First instinct: keep a single min field, updated on push.

void push(int val) { stack.push(val); min = Math.min(min, val); }

push and getMin are now O(1). But what about pop?

If you pop the element that was the minimum, you have no idea what the new minimum is. The remaining elements are in a stack, in arbitrary order — finding the new minimum means scanning all of them, which is O(n).

A minimum is not incrementally reversible. Removing an element from a sum is subtraction; removing the minimum leaves you with nothing.

That's the same obstacle as Sliding Window Maximum, and it has the same style of fix: remember more than just the current answer.

Step 2 — The reframe

Rather than asking "what is the minimum now?", ask:

"What was the minimum at the moment each element was pushed?"

If every entry carries the minimum that was true when it was pushed, then popping automatically exposes the entry beneath it — which carries the minimum that was true before the popped element existed. The restoration is free.

Step 3 — Why that's correct

The stack's contents at any moment are exactly the elements pushed and not yet popped, in order. When entry e was pushed, the elements below it were precisely the ones that are below it now — a stack never reorders. So the minimum recorded with e is still the correct minimum of everything from the bottom up to e.

That invariant is what makes the whole design work, and it's worth stating explicitly.

Step 4 — Two ways to store it

(a) Augment each entry. Store {value, minAtOrBelow} pairs. Simple, always correct, O(n) extra space with two ints per element.

(b) A second stack of minima. Push onto the min-stack only when the new value is a new minimum. Uses less space when minima are rare — but introduces the duplicate-minimum trap (§3, Approach 3).

Step 5 — The duplicate trap

With the two-stack version, consider pushing 5, 3, 3 and then popping once.

If you push onto the min-stack only when val < currentMin (strictly), the second 3 doesn't get recorded. Popping it then pops the shared 3 off the min-stack too — and getMin now reports 5, even though a 3 is still in the main stack.

The fix is <= rather than <: record every value that ties the current minimum, so each has its own entry to remove.

3. Solution Paths

Approach 1 — Scan for the minimum on demand

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();

    public void push(int val) { stack.push(val); }
    public void pop()         { stack.pop(); }
    public int top()          { return stack.peek(); }

    public int getMin() {
        int min = Integer.MAX_VALUE;
        for (int v : stack) min = Math.min(min, v);    // O(n)
        return min;
    }
}

• Time: push/pop/top are O(1); getMin is O(n).
• Space: O(n).

Counter-questions on this approach

⭐ "The problem requires O(1) for getMin. What would you need to change?"

The minimum has to be stored rather than computed. And storing just the current minimum isn't enough, because pop has to restore the previous one — so I need a record of what the minimum was at each point in the stack's history, not just now.

"Could you cache the minimum and only recompute after a pop?"

That helps the common case but not the worst case: alternating pop/getMin calls would recompute every time, so getMin is still O(n) amortized. The problem asks for a guarantee, not an average.

Approach 2 — Store the minimum alongside each value (optimal)

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();   // {value, minAtOrBelowThisPoint}

    public void push(int val) {
        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, min});
    }

    public void pop()       { stack.pop(); }
    public int top()        { return stack.peek()[0]; }
    public int getMin()     { return stack.peek()[1]; }
}

Trace — push 5, 3, 7, 2, then pop twice:

Popping restores the previous minimum with no recomputation at all — each entry already carries the answer that was correct when it was pushed.

• Time: O(1) for every operation.
• Space: O(n) — two ints per element.

Counter-questions on this approach

⭐ "You're storing the minimum n times. Isn't that wasteful?"

It doubles the memory per element, yes. The alternative — a second stack that only records new minima — uses less space when minima are rare, but it's worse when every push is a new minimum (a strictly decreasing sequence), where both approaches store n entries. So it's a trade with no clear winner, and this version has no edge cases. Given 3 × 10^4 operations, the memory is trivial either way; I'd take the simpler one.

⭐ "Why does popping correctly restore the previous minimum?"

Because a stack never reorders. The elements below an entry when it was pushed are exactly the elements below it now, so the minimum recorded with that entry is still the true minimum of everything at or below it. Popping exposes the entry beneath, which carries the minimum from before the popped element existed. The invariant maintains itself.

"Does this handle duplicate minima?"

Yes, with no special case. Pushing 3, 3 gives entries {3,3} and {3,3} — each has its own recorded minimum, so popping one leaves the other intact and getMin still reports 3. That's precisely the case where the two-stack version needs care.

"Why int[] rather than a small class or a record?"

A record Entry(int val, int min) would be more readable and is what I'd write in production. int[] avoids declaring a type and is the common interview shorthand. Either is fine; I'd mention the record if the language level allows it.

Approach 3 — Two stacks

class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> mins  = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        if (mins.isEmpty() || val <= mins.peek()) mins.push(val);   // <= , NOT <
    }

    public void pop() {
        int removed = stack.pop();
        if (removed == mins.peek()) mins.pop();
    }

    public int top()    { return stack.peek(); }
    public int getMin() { return mins.peek(); }
}

How it works. The min-stack holds only values that were a minimum (or tied one) when pushed. Popping removes from the min-stack only if the departing value was the current minimum.

• Time: O(1) for every operation.
• Space: O(n) worst case, but often much less — only O(number of distinct decreasing minima).

Counter-questions on this approach

⭐ "Why val <= mins.peek() rather than val < mins.peek()?"

Because of duplicate minima. Push 5, 3, 3. With strict <, the second 3 isn't recorded, so mins holds [3, 5]. Now pop once: the departing value is 3, which equals mins.peek(), so the 3 is popped off mins too — leaving [5]. But a 3 is still in the main stack, and getMin() now wrongly returns 5.

With <=, each tying value gets its own min-stack entry, so there's one to remove per occurrence. Verified — the strict version fails on exactly this sequence.

⭐ "Is removed == mins.peek() safe with boxed Integers?"

This is a genuine hazard. mins.peek() returns Integer, and removed is int — so the comparison auto-unboxes and compares numerically. That's safe. But if both sides were Integer, == would compare references and fail for values outside the −128..127 cache. Since val spans the full int range here, that would be a real bug. Declaring removed as int is what makes it correct. See 03.

"When is this actually better than the paired version?"

When minima are rare — a mostly-increasing sequence pushes almost nothing onto the min-stack, so memory approaches O(1) extra. When the input is strictly decreasing, every value is a new minimum and both use O(n). So it's a best-case improvement with the same worst case, bought at the cost of a subtle edge case.

Approach 4 — Single stack storing differences

class MinStack {
    private final Deque<Long> stack = new ArrayDeque<>();   // LONG, to survive the subtraction
    private long min;

    public void push(int val) {
        if (stack.isEmpty()) { stack.push(0L); min = val; }
        else {
            stack.push((long) val - min);          // encode the difference
            if (val < min) min = val;
        }
    }

    public void pop() {
        long diff = stack.pop();
        if (diff < 0) min = min - diff;            // this element WAS the minimum — restore
    }

    public int top() {
        long diff = stack.peek();
        return (int) (diff > 0 ? diff + min : min);
    }

    public int getMin() { return (int) min; }
}

How it works. Rather than storing a second value, store each element's difference from the minimum at the time of its push. A negative difference means that element became the new minimum, and its stored value encodes enough to recover the previous one.

• Time: O(1) for every operation.
• Space: O(n) — but one long per element instead of two ints.

Counter-questions on this approach

⭐ "Why long rather than int for the stored differences?"

Because val spans the full int range. If min is Integer.MIN_VALUE and val is Integer.MAX_VALUE, the difference is about 4.3 × 10^9 — which overflows int and wraps to a wrong value. Using long for both the stack and the min field is mandatory, not defensive. This is exactly the kind of constraint that's easy to miss: the trick works fine on small test values and fails on the boundary cases.

"Is this worth the complexity?"

Honestly, no — not for this problem. It saves one int per element while making the code substantially harder to verify, and the overflow hazard is a real liability. I'd mention I know it as a known optimization and ship the paired version. Knowing when not to use the clever solution is part of the answer.

Comparison

4. Why the Optimal Wins

Against scanning. The problem demands O(1), and scanning is O(n). Not a trade-off — a requirement violation.

Against a single min field. This is the instructive failure. It handles push correctly and breaks entirely on pop, because a minimum can't be un-computed. Naming that obstacle before proposing a fix is what demonstrates understanding rather than recall.

Paired entries vs two stacks. Both are O(1) on every operation. The choice is:

"The two-stack version uses less memory when minima are rare, but it has a real edge case with duplicate minima that's easy to get wrong under pressure. The paired version has no edge cases at all. With only 3 × 10⁴ operations, the memory difference is irrelevant, so I'd take the one that can't be subtly broken."

The transferable design idea:

To answer a query in O(1) on a structure that changes, store the answer alongside each element rather than maintaining it globally — so that undoing a change automatically restores the previous answer.

The same pattern gives you a max-stack, a stack with running sums, or a stack with any associative aggregate.

5. Java Prerequisites

ArrayDeque holding arrays

Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{val, min});
stack.peek()[0];      // value
stack.peek()[1];      // minimum

Generic over int[], which is an object. Note int[] would be unusable as a map key (identity equality) — but as a stack element it's fine, since nothing compares them. See 05.

A record is cleaner when available:

record Entry(int val, int min) {}
Deque<Entry> stack = new ArrayDeque<>();

Guarding the empty case on push

int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);

The first push has nothing below it, so the value is the minimum. peek() on an empty ArrayDeque returns null, and dereferencing [1] on that would throw NullPointerException.

Boxed comparison in the two-stack version

int removed = stack.pop();          // declared int — forces unboxing
if (removed == mins.peek()) ...     // int vs Integer → numeric comparison, safe

If removed were declared Integer, this would be reference comparison and would fail for values outside −128..127. Declaring it int is what makes it correct — not a style choice.

Overflow in the difference encoding

stack.push((long) val - min);       // cast BEFORE subtracting

(long) val - min promotes the whole expression to long. Writing (long)(val - min) would compute the subtraction in int first — overflowing — and then widen the already-wrong result. The cast must be on an operand, not the result.

The constraints guarantee non-empty calls

public int top() { return stack.peek()[0]; }    // no null check needed

pop, top and getMin are guaranteed to be called on a non-empty stack. Worth stating that you read that rather than adding defensive checks — or adding them and saying why you chose to.

6. Interview Communication Guide

Clarifying questions

1. "Are pop, top and getMin ever called on an empty stack?" — the constraints say no, which removes a whole class of defensive code.
2. "What should happen on duplicate values, particularly duplicate minima?" — they're allowed, and it's the edge case that breaks the two-stack version.
3. "What's the range of values?" — full int range, which matters for the difference-encoding variant.
4. "Is O(1) required for all four operations, or amortized acceptable?" — the problem says O(1), so caching-and-recomputing isn't sufficient.
5. "Is memory constrained?" — decides between paired entries and the two-stack version.

The pitch

"The difficulty isn't computing the minimum — it's that pop has to restore the previous minimum. If I track a single min field, pushing works fine, but popping the minimum leaves me with no idea what the next one is, and finding it means scanning — which is O(n).

The fix is to stop asking 'what is the minimum now' and instead record, with each element, what the minimum was when that element was pushed.

That works because a stack never reorders: the elements below an entry when it was pushed are exactly the elements below it now. So each entry's recorded minimum stays correct, and popping automatically exposes the entry beneath — which carries the minimum from before. The restoration is free.

So I'll push {value, minAtOrBelow} pairs. All four operations are O(1), space is O(n).

There's an alternative using a second stack that only records new minima — less memory when minima are rare. But it has an edge case: with duplicate minima you have to push on <= rather than <, or popping one of two equal minima removes the shared record and getMin becomes wrong. Given the operation count here, I'd take the paired version since it has no edge cases."

Edge cases to raise proactively

The duplicate-minimum sequence is the one to volunteer — push 5, 3, 3, pop, getMin should be 3, and it's the single case that distinguishes a correct two-stack implementation from a broken one.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Now support getMax as well, still O(1)."

Extend the entry to {value, min, max} — three ints instead of two, with the same reasoning. The invariant is identical: each entry records the aggregates that were true at or below it. This generalizes to any associative aggregate computable from "the value below" and "this value", such as a running sum or product.

"Make it a queue with O(1) minimum instead of a stack." (Min Queue)

Substantially harder, because a queue removes from the opposite end from where it inserts — so the "everything below me" invariant no longer holds. The standard solution is a monotonic deque holding candidate minima in increasing order, exactly like Sliding Window Maximum. O(1) amortized rather than worst case. Alternatively, implement the queue as two stacks and give each a min — which restores worst-case O(1).

"What if getMin were called far more often than push/pop?"

The paired version is already O(1) for getMin, so there's nothing to gain — the read is a single array access. Worth noting the design is already optimal for that skew rather than inventing an unnecessary change.

"What if you needed the k-th smallest, not the smallest?"

The "store it alongside" trick collapses — you'd need the whole sorted order at each level, which is O(n) per entry. You'd maintain a separate order-statistic structure such as a balanced BST or an indexed skip list alongside the stack, giving O(log n) per operation. The key insight is recognizing that the technique doesn't extend, not producing the replacement.

"What if values could be long rather than int?"

The paired and two-stack versions work unchanged — just widen the types. The difference-encoding version becomes genuinely unusable, since there's no wider primitive to absorb the subtraction; you'd need BigInteger or an explicit overflow check, which removes its only advantage.

"Make it thread-safe."

Wrap the operations in a lock, or use a lock-free design with an immutable linked-list node carrying {value, min, next} and an atomic head reference. The immutable-node version is elegant here — because each node already stores its own minimum, an atomic compare-and-set on the head gives a consistent snapshot with no locking at all.