Min Stack — O(1) getMin with Parallel Min-Tracking Stack

Problem Statement#

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

Implement the MinStack class with push(val), pop(), top(), and getMin().

Constraints:

• -2^31 <= val <= 2^31 - 1
• Methods pop, top, and getMin will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Input:  ["MinStack","push","push","push","getMin","pop","top","getMin"]
        [[],[-2],[0],[-3],[],[],[],[]]
Output: [null,null,null,null,-3,null,0,-2]
Explanation:
MinStack minStack = new MinStack();
minStack.push(-2);  // stack: [-2]
minStack.push(0);   // stack: [-2, 0]
minStack.push(-3);  // stack: [-2, 0, -3]
minStack.getMin();  // return -3
minStack.pop();     // stack: [-2, 0]
minStack.top();     // return 0
minStack.getMin();  // return -2

Input:  ["MinStack","push","push","getMin","pop","getMin"]
        [[],[2],[1],[],[],[]]
Output: [null,null,null,1,null,2]

Input:  ["MinStack","push","getMin","pop","push","getMin"]
        [[],[5],[],[],[3],[]]
Output: [null,null,5,null,null,3]

Why This Problem Matters#

LC 155 is one of the most frequently asked stack design problems at Amazon, Google, Bloomberg, and Microsoft. It tests a critical design principle: maintaining auxiliary state in sync with the primary data structure to make expensive queries O(1).

In production systems, this exact pattern appears in undo/redo systems (tracking not just the state but also the best/worst state seen), in trading systems that need real-time minimums and maximums, and in database query planners that track statistics alongside data.

The problem forces you to think about what invariant the auxiliary structure must maintain, and how to keep it in sync with every push and pop. Interviewers follow this with "what if you need getMax too?" (add a max stack) and "can you do it with O(1) extra space?" (use value encoding trick — store min_so_far alongside values).

The Core Insight#

The naive approach — iterating over the stack to find the minimum — costs O(n) per getMin call. We need O(1).

Key insight: maintain a parallel min_stack where min_stack[i] stores the minimum value in the main stack considering elements from index 0 through i. When we push a new element, the new minimum is min(new_value, current_min). When we pop, we pop from both stacks simultaneously — the min stack stays in perfect sync with the main stack.

This works because: at any moment after n pushes and k pops, the minimum of the current stack is exactly min_stack.top(). Each pop restores the minimum to what it was before the last push.

Alternative: store pairs. Each stack entry is (value, min_so_far). Same idea, single stack.

Visual Dry Run#

Operations: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Notice: after popping -3, the min correctly reverts to -2. The parallel min stack makes this O(1).

Solution (Optimal)#

# Python — parallel min stack, all operations O(1)
class MinStack:
    def __init__(self):
        self.stack = []      # main stack of values
        self.min_stack = []  # parallel stack: min_stack[i] = min(stack[0..i])
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        # New min is either this value or the current minimum
        if self.min_stack:
            self.min_stack.append(min(val, self.min_stack[-1]))
        else:
            self.min_stack.append(val)  # first element is its own minimum
 
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()  # always pop both in sync
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]  # always O(1)

// JavaScript — parallel min stack, all operations O(1)
class MinStack {
    constructor() {
        this.stack = [];       // main stack of values
        this.minStack = [];    // parallel: minStack[i] = min(stack[0..i])
    }
 
    push(val) {
        this.stack.push(val);
        if (this.minStack.length > 0) {
            this.minStack.push(Math.min(val, this.minStack[this.minStack.length - 1]));
        } else {
            this.minStack.push(val);
        }
    }
 
    pop() {
        this.stack.pop();
        this.minStack.pop();   // always pop both simultaneously
    }
 
    top() {
        return this.stack[this.stack.length - 1];
    }
 
    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

Complexity:

Common Mistakes#

1. Forgetting to pop from the min stack on every pop. The two stacks must always have the same size. If you pop only from the main stack, the min stack becomes stale and getMin returns wrong values.

2. Storing only the current global minimum. If you track a single min_val variable and pop an element that equals min_val, you lose track of the previous minimum. The parallel stack solves this.

3. Not handling the empty min_stack case on the first push. On the very first push, there is no previous minimum. Always handle this: use val itself as the minimum, or initialize min_stack with float('inf').

4. Updating min on push but not restoring on pop. Some candidates track minimum correctly on push but do not realize popping requires reverting the minimum to the previous value. The parallel stack handles restoration automatically.

5. Using a sorted structure. Storing elements in a sorted set gives O(log n) getMin, not O(1). The parallel stack is the right approach for O(1).

Interview Tips#

• Name the invariant explicitly: "At position i in the min stack, I store the minimum of all elements from index 0 through i in the main stack. This invariant holds after every push and every pop."
• Mention the space trade-off: "I use O(n) extra space to get O(1) time. If space is critical, I can use a single stack storing (value, min) pairs — same space, cleaner API."
• If asked about getMax: add a symmetric max_stack — same structure, same O(1) performance.
• If asked about O(1) extra space: use the encoding trick — store (val - current_min) to detect when min changes; a negative stored value means a new minimum was set.

Follow-up Questions#

1. Design a Max Stack that also supports getMax in O(1). Add a parallel max_stack with the same structure.
2. Can you achieve O(1) extra space? Store encoded deltas; when you pop an element that beats the stored min, decode the previous min. Requires careful handling of integer overflow.
3. What if you need the k-th minimum? Use a sorted structure alongside the stack — O(log n) per operation.
4. Design a stack with O(1) median. Use two heaps (max-heap for lower half, min-heap for upper half); rebalance on push and pop.
5. Thread-safe MinStack. Wrap push/pop/getMin in mutex locks; or use compare-and-swap for a lock-free version.

Key Takeaways#

• The parallel min stack is the canonical O(1) solution: min_stack[i] stores the running minimum through index i, so getMin() is just a peek at the top.
• Both stacks must always have equal size — pop from both simultaneously on every pop() call.
• This is a direct application of the stack invariant principle: maintain auxiliary state in sync with every push and pop so that expensive queries become O(1).
• The pattern extends to getMax (parallel max stack), getMedian (two heaps), and getKthSmallest (order statistics tree).
• In interviews, state the invariant clearly before writing code — it demonstrates structured thinking and prevents common bugs.
• Alternative encoding with pairs (value, min_so_far) uses a single stack and is slightly more space-efficient in practice.