A blotter of open limit orders is a LIFO buffer: last ticket in is the first the desk can cancel. Risk still wants the cheapest remaining order on every tick, not after a walk of the whole book. The intern version scanned the stack on every getMin. A quiet session looked fine. A live book made the status bar a linear scan on the hot path.

Min Stack asks for push, pop, top, and the current minimum in O(1). One deque already gives the top for free. Scanning remaining values on getMin uses that and still pays linear time on the hot path.

This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why the top is the only cheap end. Here we only care about answering the current minimum among values still on the stack without starting a scan.

The problem

Implement a stack with four operations. push(x) puts x on top. pop() removes the top. top() returns the top without removing it. getMin() returns the smallest value among elements that are still on the stack. Every operation must be constant time.

A short session:

push(3)   top=3   getMin=3
push(5)   top=5   getMin=3
push(2)   top=2   getMin=2
push(2)   top=2   getMin=2
pop()     top=2   getMin=2
pop()     top=5   getMin=3

Note: Empty pop / top / getMin is a contract question, not a design one. Ask whether the prompt promises a non-empty stack. At the board, do not invent a sentinel unless they ask.

Scan on getMin is the honest brute force

Keep one deque of values. push, pop, and top are already O(1); getMin walks every remaining element and tracks the smallest. Correct, linear, and it fails the O(1) contract the moment the stack is taller than a handful of frames.

class MinStackScan {
    Deque<Integer> values = new ArrayDeque<>();

    void push(int x) {
        values.push(x);
    }

    void pop() {
        values.pop();
    }

    int top() {
        return values.peek();
    }

    int getMin() {
        int min = Integer.MAX_VALUE;
        for (int v : values) {
            min = Math.min(min, v);
        }
        return min;
    }
}

Scanning on getMin is the intern blotter: you paid for a running min you never stored. Interviewers let you say this out loud, then they want the second deque.

Two deques: values and the floor at this height

values is the real stack. mins stores the floor at each height where that floor changed — or repeated. On push(x), always push onto values. Push onto mins only when mins is empty or x <= mins.peek(). On pop(), pop values. If the popped value equals mins.peek(), pop mins too. getMin() is mins.peek().

The <= is the whole trick. A second copy of the current floor must land on mins, or the first pop of that value uncovers a stale floor.

Walk the same session. Bottom is on the left; top is on the right.

push(3)  values [3]           mins [3]         getMin=3
push(5)  values [3, 5]        mins [3]         getMin=3   // 5 > 3, mins unchanged
push(2)  values [3, 5, 2]     mins [3, 2]      getMin=2   // 2 <= 3, push 2
push(2)  values [3, 5, 2, 2]  mins [3, 2, 2]   getMin=2   // 2 <= 2, push again
pop()    values [3, 5, 2]     mins [3, 2]      getMin=2
pop()    values [3, 5]        mins [3]         getMin=3

If the second push(2) had skipped mins because “we already know the min is 2”, the first pop would take the only 2 off mins and getMin would return 3 while a 2 was still on values.

The Java is those two deques:

class MinStack {
    Deque<Integer> values = new ArrayDeque<>();
    Deque<Integer> mins = new ArrayDeque<>();

    void push(int val) {
        values.push(val);
        if (mins.isEmpty() || val <= mins.peek()) {
            mins.push(val);
        }
    }

    void pop() {
        int x = values.pop();
        if (x == mins.peek()) {
            mins.pop();
        }
    }

    int top() {
        return values.peek();
    }

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

Every operation is O(1) — one or two deque ops, no scan. Space is O(n) in the worst case: a strictly decreasing input fills mins as full as values. The always-push-running-min variant — push Math.min(val, mins.peek()) on every push, pop both deques together — is also O(1) and O(n); it spends a slot on mins for every height. The sparse <= version is the one that surfaces the duplicate-min bug; the always-push variant never has to think about it.

Forgetting to push a duplicate min is the usual miss. x < mins.peek() looks cleaner and fails the second push(2) in the trace. Unbox to int before comparing the popped value to mins.peek() so Integer identity does not bite you on values outside the cached range.

What interviewers usually poke next

  • Max stack. Same two deques, >= instead of <=. No new idea.
  • O(1) extra space with encoded diffs. Store x - currentMin (or a similar encoding) on a single stack and recover the old min on pop. It is a trick, not the default; overflow and readability are the cost. Mention it if they ask for less space, then go back to two deques.
  • Empty pop / top / getMin. The prompt usually promises a non-empty stack. In production you would reject; at the board, ask.
  • Related design: Implement Queue using Stacks — two stacks for FIFO. Do not solve it here; the shared move is pairing two LIFO structures to buy a cheap extra operation.

You are done with this problem when you can say, out loud, why a scan on getMin fails the contract, why mins must receive a second copy of the same floor, and why <= is not <.