Min Stack

MEDIUM✓ CHIP-TIMEDLC #155 — FULL STATEMENT ↗

The drill: A stack that can also report its smallest element — push, pop, top and getMin, all in constant time. The whole question is what extra you store to make min free.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Build a stack with one extra talent: at any moment it can name the smallest value it currently holds. Four operations — push a value, pop the top, read the top, and getMin — and every one of them must run in constant time.

The stack behaves normally in every other way: values go in and come out last-in-first-out, duplicates are allowed, and getMin reports the minimum of what is on the stack right now, not of everything it has ever seen.

The trap is pop: when the current minimum leaves, the stack must already know what the minimum was before it arrived — recomputing it by scanning would blow the constant-time budget.

EX 01

MinStack()

push(4)

push(2)

getMin() → 2

pop()

getMin() → 4

MIN RESTORES AFTER POP

EX 02

MinStack()

push(3)

pop()

getMin() → 3

DUPLICATE MINIMUMS

EX 03

MinStack()

push(9)

push(7)

push(5)

getMin() → 5

pop()

getMin() → 7

pop()

getMin() → 9

DESCENDING PUSHES

push, pop, top and getMin must all be O(1)
values can be negative, zero, or positive, duplicates included
pop and top are only called while the stack is non-empty
getMin reflects the current contents, not history

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Recomputing the minimum after a pop is what breaks constant time. What could each element carry so nothing ever needs recomputing?

HINT 2 THE STRUCTURE

The minimum only changes at pushes and pops. Track its history, not just its current value.

HINT 3 ONE STEP FROM THE ANSWER

Keep a second stack of “minimum so far”: push min(new, its top) on every push, pop both together. getMin is its top, always.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SHADOW MINIMUMPATTERN · SHADOW MIN STACKpush(4) · push(2) · getMin() · pop() · getMin()

push 4

push 2

getMin

pop

getMin

ITEMS / MINS

— empty —

STEP 1

A shadow stack tracks the minimum at every depth — push min(new, its own top), pop both together.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/min-stack.py — RACE PACE

LANG ▸

PACE ▸

class MinStack:
    def __init__(self):
        self.items = []
        self.mins = []

    def push(self, val: int) -> None:
        self.items.append(val)
        self.mins.append(val if not self.mins else min(val, self.mins[-1]))

    def pop(self) -> None:
        self.items.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.items[-1]

    def getMin(self) -> int:
        return self.mins[-1]

TIME O(1) ALL OPSSPACE O(N)PYTHON · RACE PACE · 18 LN

class MinStack:
    def __init__(self):
        self.items = []

    def push(self, val: int) -> None:
        self.items.append(val)

    def pop(self) -> None:
        self.items.pop()

    def top(self) -> int:
        return self.items[-1]

    def getMin(self) -> int:
        return min(self.items)

TIME O(N) GETMINSPACE O(N)PYTHON · TRAINING PACE · 15 LN

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

    public MinStack() {
    }

    public void push(int val) {
        items.push(val);
        mins.push(mins.isEmpty() ? val : Math.min(val, mins.peek()));
    }

    public void pop() {
        items.pop();
        mins.pop();
    }

    public int top() {
        return items.peek();
    }

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

TIME O(1) ALL OPSSPACE O(N)JAVA · RACE PACE · 25 LN

class MinStack {
    private final List<Integer> items = new ArrayList<>();

    public MinStack() {
    }

    public void push(int val) {
        items.add(val);
    }

    public void pop() {
        items.remove(items.size() - 1);
    }

    public int top() {
        return items.get(items.size() - 1);
    }

    public int getMin() {
        int best = items.get(0);
        for (int v : items) {
            best = Math.min(best, v);
        }
        return best;
    }
}

TIME O(N) GETMINSPACE O(N)JAVA · TRAINING PACE · 26 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED