Design a min stack

A stack that also knows its minimum — instantly

Build a stack with three operations, all in O(1): push a value, pop the top, and return the current minimum. Push and pop are trivial on any stack. The hard constraint is findMin() in constant time.

Scanning is O(N); one variable forgets

Scanning the stack for its smallest value is O(N) — banned by the requirement. So keep a running min variable? Push handles it fine with min(oldMin, x). But pop breaks it:

Push 5, 3 → min is 3. Pop the 3 and the stack is [5], so the min should be 5 — but a single variable never recorded it. The real need is minimum history: what was the minimum before each element arrived.

Keep a running record, not a single number

Two stacks, moving in lockstep

Push values and pop them. The main stack holds your values; the min stack pushes min(x, currentMin) alongside every value. Watch how the top of the min stack is always the answer to findMin() — and how popping restores the previous minimum for free.

The invariant that makes it O(1)

Push 2, 3, 1, 4 and the minimum after each push is 2, 2, 1, 1. The two stacks line up slot for slot:

Because each value carries its own paired minimum, popping never requires a recompute — remove the top of both stacks and the previous minimum is sitting right there.

Two parallel stacks

import java.util.*;

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

    void push(int x) {
        stack.push(x);
        if (minStack.isEmpty()) minStack.push(x);
        else minStack.push(Math.min(x, minStack.peek()));
    }

    void pop() {
        if (stack.isEmpty()) return;
        stack.pop();
        minStack.pop();            // stay in lockstep
    }

    int findMin() {
        return stack.isEmpty() ? -1 : minStack.peek();
    }
}

Every operation is a constant number of stack calls, so push, pop, and findMin are all O(1). Both stacks hold up to N items, giving O(N) space — the classic trade of memory for query speed. Prefer ArrayDeque over the legacy Stack class.

If you compress the min stack, use <=

A space-saving variant pushes to the min stack only when a value is a new minimum, and pops it only when the popped value equals the current min. It works — but the comparison must be <=, not <.

// sparse variant — note the <=
void push(int x) {
    stack.push(x);
    if (minStack.isEmpty() || x <= minStack.peek()) minStack.push(x);
}
void pop() {
    int removed = stack.pop();
    if (removed == minStack.peek()) minStack.pop();
}

It's still O(N) in the worst case — a strictly decreasing input makes every value a new minimum. For learning, the push-to-both version is safer; the compression just trades a little clarity for occasional space.

Store the min inside each entry

Two parallel stacks and one stack of (value, minSoFar) pairs are the same idea wearing different clothes. Each entry carries the minimum as of when it was pushed, so the top always knows the current minimum.

record Entry(int value, int minSoFar) {}

Deque<Entry> stack = new ArrayDeque<>();

void push(int x) {
    int m = stack.isEmpty() ? x : Math.min(x, stack.peek().minSoFar());
    stack.push(new Entry(x, m));
}
int findMin() { return stack.isEmpty() ? -1 : stack.peek().minSoFar(); }

Augment the structure with state at every depth

This isn't really about minimums. It's a template: whenever a data structure needs an extra aggregate query in O(1), store that aggregate at every depth so it updates incrementally. The recurrence is always state[i] = combine(state[i−1], newValue).

The same instinct powers prefix sums, segment trees, and augmented trees: store extra information when maintaining it beats recomputing it later.

Reconstruct it from one question

1. A normal stack gives push and pop in O(1), but min needs a scan — O(N).
2. To answer instantly, maintain the minimum as the stack changes.
3. One variable fails: popping the min loses the previous min.
4. So I need minimum history — and history in LIFO order is a stack.
5. Push value and min-so-far together; pop both; findMin is the min stack's top.