Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Min Stack
• Main tags: Stack, Design

What the problem is really asking

The API looks simple: push, pop, top, and getMin.

The real requirement is hidden in getMin: it must return the current minimum in constant time, not by scanning the whole stack.

That means a plain stack is not enough by itself. The stack has to carry extra information so that every stack state already knows its own minimum.

The first correct idea

A straightforward first solution is to store the values in a normal stack and compute the minimum by scanning all elements whenever getMin is called.

That is correct, but it makes getMin cost O(n) time. The interview version of this problem expects all four operations to be O(1), so repeated scans are too expensive.

Once that is clear, the next question is:

“When can the minimum actually change?”

Only when the stack changes through push or pop. That observation points to the right design: update minimum information during mutations so queries stay cheap.

The optimal design

The cleanest solution is to store, for every pushed value, the minimum value in the stack at that exact moment.

So instead of pushing just:

value

the stack pushes:

(value, minimum_so_far)

For example, if the current minimum is -2 and 0 is pushed, the new entry becomes:

(0, -2)

If -3 is pushed next, the new entry becomes:

(-3, -3)

Now every operation is immediate:

• push: compare the new value with the previous minimum and store the new minimum alongside it
• pop: remove the top pair
• top: read the top pair’s value
• getMin: read the top pair’s cached minimum

This works because the top entry always represents the full current state of the stack.

A concrete example

Start with an empty stack.

Push -2:

[(-2, -2)]

Push 0:

[(-2, -2), (0, -2)]

Push -3:

[(-2, -2), (0, -2), (-3, -3)]

Now getMin() returns -3 immediately from the top entry.

If pop() removes (-3, -3), the stack becomes:

[(-2, -2), (0, -2)]

Now getMin() returns -2, again directly from the top entry.

Nothing has to be recomputed because each stack level already cached the correct minimum for its own prefix.

How to derive this in an interview

A strong interview explanation usually goes in this order:

1. Start with the obvious stack and notice that getMin would need a full scan.
2. Point out that the minimum changes only on push and pop.
3. Decide to pay the cost during mutation instead of during query.
4. Store the running minimum with each entry so the current stack minimum is always available at the top.

That reasoning shows the design was derived from the constraint, not memorized.

Python solution

from dataclasses import dataclass
from typing import List


@dataclass(frozen=True)
class StackEntry:
    value: int
    minimum_so_far: int


class MinStack:
    """
    Stack with O(1) push, pop, top, and getMin operations.
    """

    def __init__(self) -> None:
        self._entries: List[StackEntry] = []

    def _ensure_not_empty(self) -> None:
        if not self._entries:
            raise IndexError("MinStack is empty")

    def push(self, val: int) -> None:
        # Cache the minimum that should be visible after this push.
        current_minimum = (
            val
            if not self._entries
            else min(val, self._entries[-1].minimum_so_far)
        )
        self._entries.append(
            StackEntry(value=val, minimum_so_far=current_minimum)
        )

    def pop(self) -> None:
        self._ensure_not_empty()
        self._entries.pop()

    def top(self) -> int:
        self._ensure_not_empty()
        return self._entries[-1].value

    def getMin(self) -> int:
        self._ensure_not_empty()
        return self._entries[-1].minimum_so_far

Why this works

The key invariant is:

every entry stores the minimum of the stack prefix ending at that entry.

That invariant is true at the start because the first pushed value is its own minimum. It stays true on each later push because the new entry stores:

min(new_value, previous_minimum)

So the top entry always knows the minimum for the entire current stack.

Pop is also safe under the same invariant. Removing the newest entry exposes the previous one, whose cached minimum was already correct for the older stack state.

Because each method touches only the top of the stack, every operation runs in O(1) time. The extra space is O(n) because one cached minimum is stored per pushed element.

Interview follow-ups

Could this be implemented with two stacks instead of one stack of pairs?

Yes. One common version keeps a normal value stack and a separate min stack. On each push, the value goes to the main stack, and the min stack either receives the new value if it is a new minimum or repeats the current minimum so both stacks stay aligned. Then getMin reads the top of the min stack. This works for the same reason as the pair-based design: every stack depth has direct access to the correct minimum. The tradeoff is mostly stylistic. Two stacks and one stack of pairs have the same asymptotic complexity, but the pair version keeps related data together in one structure.

What if there are duplicate minimum values?

Duplicates are the place where weak designs often break. Suppose the minimum is 2, and another 2 is pushed. If the implementation only tracks strictly smaller values, then popping one 2 could incorrectly lose the fact that another 2 is still present. The pair-based solution handles this automatically because each push stores the minimum visible at that depth, even when the minimum does not change. A two-stack solution also works if it either pushes duplicate minimums or stores counts for each minimum. The important idea is that minimum state must reflect multiplicity, not just distinct values.

What if the interviewer also wants getMax() in constant time?

The same pattern extends directly. Each stack entry can store both minimum_so_far and maximum_so_far, or the implementation can maintain a separate max stack. Then push updates both summaries, pop removes both, top still reads the value, and getMin and getMax both become O(1). The reason this works is that minimum and maximum are both prefix summaries that can be updated from the previous stack state using only the new value. The tradeoff is slightly more memory per entry, but the asymptotic complexity stays the same.

Can the extra space be reduced below O(n)?

Not in the general worst case if all operations must stay O(1). Every stack state may need to remember a different minimum, especially in sequences where values keep decreasing. A two-stack approach that stores only changed minima with counts can reduce constant factors when the minimum changes rarely, but the worst-case space is still linear. That is the core tradeoff: to make getMin constant time, the implementation has to preserve enough history to restore the correct minimum after arbitrary pops.

Practical takeaway

This problem is a classic example of augmenting a data structure with cached summary information.

The winning move is to store each value together with the minimum seen up to that depth. Once that invariant is in place, all required operations become simple top-of-stack reads or writes.