Free lesson · DSA Mastery - Interview Prep, End to End

Min Stack

Medium6 min readdsastacks

Min Stack

Min Stack pushes in the opposite direction from the depth problem: design a stack that supports push, pop, top, and retrieving the minimum element - all in O(1). The naive idea (scan for the minimum on demand) is O(n) per query; the trick is to augment the stack so each entry also remembers the minimum at or below it. We present two approaches: a two-stack design (a main stack plus a parallel min-tracking stack) and a single stack of pairs (each entry stores both its value and the running minimum). Both achieve O(1) for every operation.

The key realization: the minimum of a stack only changes on push and pop, and it depends only on the elements currently present. By storing "the min at or below me" with each element, popping automatically restores the previous minimum for free.

The Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example:

MinStack s = new MinStack();
s.push(-2);
s.push(0);
s.push(-3);
s.getMin();   // return -3
s.pop();
s.top();      // return 0
s.getMin();   // return -2

Constraints:

• -2^31 <= val <= 2^31 - 1
• Methods pop, top, getMin are always called on non-empty stacks.
• At most 3·10^4 calls in total.

Approaches Overview

Both give O(1) per operation by storing minimum information alongside the values. The two-stack version keeps mins in a parallel stack; the pair version bundles each value with the min-so-far. Same idea, two packagings.

Approach 1: Two Stacks - Standard

The Idea

Keep a main stack of values and a parallel minStack whose top is always the current minimum. On push(val): push val to the main stack, and push min(val, minStack.peek()) to minStack (or val if empty). On pop: pop both. getMin returns minStack.peek(); top returns stack.peek(). Because both stacks move together, the min stack's top always reflects the minimum of exactly the elements currently in the main stack - and popping restores the previous min automatically.

Logic Flowchart

graph TD
    A["push(val)"] --> B["stack.push(val)"]
    B --> C["m = minStack.empty ? val : min(val, minStack.peek())"]
    C --> D["minStack.push(m)"]
    E["pop()"] --> F["stack.pop(); minStack.pop()"]
    G["getMin()"] --> H["return minStack.peek()"]
    I["top()"] --> J["return stack.peek()"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style J fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two-stack design. Push adds the value to the main stack and the smaller of the value and the current minimum to the min stack. Pop removes from both. Get-min returns the min stack's top, and top returns the main stack's top.

Code

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

    public void push(int val) {
        stack.push(val);
        int curMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
        minStack.push(curMin);
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

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

// Usage:
// push(-2); push(0); push(-3); getMin() -> -3; pop(); top() -> 0; getMin() -> -2

This Java class keeps a main stack and a min stack. Push stores the value and the running minimum in parallel. Pop removes from both. Get-min returns the min stack's top and top returns the main stack's top, each in constant time.

Step-by-Step Walkthrough

A frame-by-frame trace of the example operations:

graph LR
    F0["push -2<br/>val:[-2] min:[-2]"]
    F1["push 0<br/>val:[-2,0] min:[-2,-2]"]
    F2["push -3<br/>val:[-2,0,-3] min:[-2,-2,-3]<br/>getMin=-3"]
    F3["pop<br/>val:[-2,0] min:[-2,-2]<br/>top=0"]
    F4["getMin = -2"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough pushes minus two, zero, minus three. The min stack tracks minus two, minus two, minus three, so get-min returns minus three. After popping minus three, top is zero and the min stack's top is minus two, so get-min returns minus two.

Result: getMin returns -3, then after pop, top is 0 and getMin is -2.

Complexity

Time: O(1) per operation. Space: O(n) - two stacks of n elements.

Approach 2: Single Stack of (val, min) Pairs

The Idea

Use one stack where each entry is a pair (value, minSoFar). On push(val), compute minSoFar = min(val, currentTop.minSoFar) (or val if empty) and push the pair. top reads the pair's value; getMin reads the pair's minSoFar. Identical logic to two stacks, but bundled into one structure - handy in languages where a second stack feels heavy, or to make the coupling explicit.

Logic Flowchart

graph TD
    A["push(val)"] --> B["m = empty ? val : min(val, peek().min)"]
    B --> C["push pair (val, m)"]
    D["pop()"] --> E["stack.pop()"]
    F["top()"] --> G["return peek().val"]
    H["getMin()"] --> I["return peek().min"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the single-stack design. Each pushed entry is a pair of the value and the minimum so far. Pop removes the top pair. Top returns the pair's value and get-min returns the pair's stored minimum.

Code

class MinStackPairs {
    private final Deque<int[]> stack = new ArrayDeque<>();   // [value, minSoFar]

    public void push(int val) {
        int m = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[]{val, m});
    }

    public void pop() { stack.pop(); }

    public int top() { return stack.peek()[0]; }

    public int getMin() { return stack.peek()[1]; }
}

This Java class stores each entry as a two-element array of the value and the minimum so far. Push computes the new minimum and stores the pair; pop removes the top; top and get-min read the value and stored minimum respectively.

Complexity

Time: O(1) per operation. Space: O(n).

Complexity Comparison

Both are O(1) per operation and O(n) space - the cost of storing min information. They're the same algorithm; pick whichever reads better to you. (A space optimization stores mins only when they change, but it complicates pop and isn't worth it for typical inputs.)

Variations & Follow-ups

Why does storing "min at or below me" make pop O(1)?

Each element records the minimum of the stack as it was when that element was on top. Popping it exposes the element beneath, whose stored min is exactly the minimum of the remaining stack - no recomputation needed.

Could you store mins only when they decrease (space optimization)?

Yes - push to the min stack only when val <= currentMin, and pop from it only when the popped value equals the current min. This saves space when many pushes don't change the min, at the cost of trickier pop logic and careful handling of duplicate minimums.

How would you also support O(1) getMax?

Symmetrically - keep a parallel max stack (or extend the pair to (val, min, max)). The technique generalizes to any associative "running aggregate" that's well-defined over a suffix of pushes.

What about edge cases?

• Duplicate minimums: Both copies store the same min; popping one correctly leaves the other as the min (handle with <= in the space-optimized variant).
• Single element: Its min is itself.
• Monotonically increasing pushes: Min stack repeats the first (smallest) value.
• Overflow values (2^31 range): Use int/long carefully; comparisons are fine within int.

Common Interview Pitfalls

• Recomputing the min by scanning. That's O(n) per getMin - defeats the requirement.
• Forgetting to pop the min stack alongside the main stack. They must stay in lockstep.
• Mishandling the empty case on push. First push seeds the min with the value itself.
• In the space-optimized variant, using < instead of <=. Duplicate minimums break if you don't push/pop them consistently.

Why This Problem Matters

Min Stack is the canonical lesson in augmenting a structure with O(1) auxiliary state: by storing a running aggregate alongside each element, you answer a query that would otherwise be O(n) in constant time. This "carry extra state with each entry" technique recurs in monotonic stacks (which carry order), in Online Stock Span, and in many design problems where a clever invariant replaces a scan.

The next topic, Remove Duplicate Letters, raises the difficulty sharply: build the lexicographically smallest result that contains each distinct letter exactly once, by greedily popping larger letters off the stack when a smaller one arrives - provided the popped letter appears again later. It's the first problem where the stack enforces an ordering goal, foreshadowing the monotonic stack.

Back to DSA Mastery - Interview Prep, End to End