Design a Stack that supports getMin() in O(1) time and O(1) extra space

The problem, simply

Build a stack with push(x), pop(), top() and one more action, getMin(), which gives the smallest number in the stack right now.

All four must take O(1) time. The hard version also says: use only O(1) extra room. You may keep the stack itself, but not a second stack beside it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a second pile next to the first. Each time you push x, also push "the smallest so far" onto the second pile. Each time you pop, pop both piles.

1. push(x): push x on the main pile. Push min(x, minPile.top) on the min pile.
2. pop(): pop both piles.
3. getMin(): read the top of the min pile.

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

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

    public void pop() {
        main.pop();
        mins.pop();            // both piles always have the same height
    }

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

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

How long it takes: every action is O(1). Extra room: a second pile as tall as the first, O(n).

Way 2: the clever way

Keep only one pile and one number, min. When a new value is not a new low, push it as it is. When it is a new low, we must remember the old min somewhere, so we push a special note instead:

• note = 2 * x - min

Because x < min, the note is smaller than x. Every real value on the pile is at least the current min, so a stored value below min must be a note.

1. push(x): if the pile is empty, push x and set min = x. Else if x < min, push 2 * x - min and set min = x. Else push x.
2. top(): if the stored top is below min, it is a note, and the real value is min. Otherwise it is the real value.
3. pop(): if the popped value y is below min, it was a note, so the old minimum comes back: min = 2 * min - y.
4. getMin(): return min.

Why does the math work? We stored y = 2x - old, and min became x. So 2 * min - y = 2x - (2x - old) = old.

class MinStackO1 {
    private final Deque<Long> pile = new ArrayDeque<>();
    private long min;

    public void push(int x) {
        if (pile.isEmpty()) {
            pile.push((long) x);
            min = x;
        } else if (x < min) {
            pile.push(2L * x - min);   // a note that hides the old min
            min = x;
        } else {
            pile.push((long) x);
        }
    }

    public void pop() {
        long y = pile.pop();
        if (y < min) min = 2 * min - y; // it was a note: bring the old min back
    }

    public int top() {
        long y = pile.peek();
        return (int) (y < min ? min : y);
    }

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

How long it takes: every action does a little math, O(1). Extra room: one number, min, so O(1) beyond the pile itself.

Watch out for

• Order matters in push. Work out the note with the old min first, then set min = x. Doing it the other way round stores 2x - x = x, and the old minimum is lost.
• top() must decode too. If the stored top is a note, the real value is min.
• Calling pop, top or getMin on an empty stack. Agree with the interviewer: throw, or return a sentinel.

What interviewers ask next

• Can you save space in the two pile version? Push to the min pile only when x <= minPile.top, and pop it only when the popped value equals its top. Ties need the <=, or the min pile loses a copy too early.
• Can you do getMax()? Yes, flip it: when x > max, store 2 * x - max, and a stored value above max is a note.
• Store pairs instead. Push (x, minSoFar) together. Clean and easy to explain, but it is the same O(n) extra room as Way 1.
• A queue with getMin() in O(1). Build the queue from two min stacks. Each value is moved between them at most once, so it is amortized O(1).
• Why is the second way rarely used in production? It only works for numbers you can do math on, and it is easy to get overflow wrong. Interviewers ask it to see if you can reason about invariants.

Remember this

Grown-up words: the clipboard is the min variable, the special ticket is an encoded value, the second pile in Way 1 is an auxiliary min stack, and "everything real is at least min" is the invariant that makes notes easy to spot.