Design Min Stack — O(1) Minimum with Auxiliary Stack

Problem Statement#

Design a stack supporting push(val), pop(), top(), and getMin(). All four operations must run in O(1) time and O(1) amortised space per operation.

Constraints:

• -2^31 <= val <= 2^31 - 1
• pop, top, and getMin are always called on a non-empty stack
• At most 3 * 10^4 calls total

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

Input:  push(1), push(2), getMin(), pop(), getMin()
Output: 1, 1

Why This Problem Matters#

Min Stack is one of the most commonly asked warm-up problems at Amazon, Google, and Meta because it tests a fundamental design principle: augmenting a data structure to track auxiliary information in O(1). This same pattern—maintaining a parallel tracking structure—appears in sliding window maximum (monotonic deque), LRU cache (hashmap + doubly linked list), and histogram area problems.

In production systems, expression evaluators, syntax parsers, and undo/redo buffers all use stack augmentation to track runtime statistics efficiently. Understanding this pattern prepares you for a class of problems that require enhancing standard data structures without changing their asymptotic complexity.

The min stack problem also tests whether you know that finding the minimum naively requires O(N) traversal—and that a constant-time solution requires storing additional information alongside the data.

The Core Insight#

Maintain two stacks in parallel: the main stack for values and a min_stack that tracks the running minimum at each depth. When pushing a value, also push min(val, min_stack.top()) to the min stack (or just val if the min stack is empty). When popping, pop from both stacks. getMin() returns min_stack.top().

The insight is that each position in the min stack records the minimum of all elements at or below that depth—so as you push and pop, the minimum is always correct at the current stack depth without any traversal.

An alternative single-stack approach encodes the minimum alongside each value, but the two-stack approach is cleaner and more interview-ready.

Visual Dry Run#

Solution (Optimal)#

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        min_val = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(min_val)
 
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]

class MinStack {
    constructor() {
        this.s = [];
        this.m = [];
    }
 
    push(v) {
        this.s.push(v);
        const cur = this.m.length ? Math.min(v, this.m[this.m.length - 1]) : v;
        this.m.push(cur);
    }
 
    pop() {
        this.s.pop();
        this.m.pop();
    }
 
    top() {
        return this.s[this.s.length - 1];
    }
 
    getMin() {
        return this.m[this.m.length - 1];
    }
}

Time: O(1) for all four operations
Space: O(N) — two stacks, each storing at most N elements

Common Mistakes#

• Storing only the global minimum rather than the running minimum at each depth—this fails when the current minimum is popped
• Pushing val to the min stack regardless of whether val is a new minimum—this is wasteful but still correct; the cleaner approach pushes min(val, current_min) always
• Not handling the empty min_stack case on push—accessing min_stack[-1] on an empty list raises IndexError in Python
• Confusing top() (peek at main stack top) with getMin() (peek at min stack top)
• In the single-stack variant, integer overflow when encoding the minimum alongside the value using arithmetic tricks

Interview Tips#

• Draw the two stacks side by side during your explanation—this makes the invariant immediately obvious
• State the invariant explicitly: "At any depth i, min_stack[i] equals the minimum of all values from the bottom to depth i"
• Mention the space trade-off: this uses 2x space; the single-stack arithmetic trick uses 1x space but risks overflow for large values
• This problem generalises to Max Stack, which uses a parallel max stack with identical logic

Follow-up Questions#

• How would you implement a Max Stack with O(1) getMax? (Identical approach with a parallel max stack tracking running maximum)
• How would you implement a stack that supports both getMin and getMax in O(1)? (Two auxiliary stacks: one for min, one for max)
• How would you reduce space from O(N) to O(1) auxiliary space? (Only push to min_stack when a new minimum is encountered; pop from it only when the current min is popped—requires storing counts)
• Can you implement Min Stack using a single stack? (Store pairs (value, current_min) in each stack element)
• How would you implement a Min Queue (not stack)? (Use two Min Stacks—one for enqueue, one for dequeue; transfer on empty dequeue side)

Key Takeaways#

• Two parallel stacks give O(1) push, pop, top, and getMin without any traversal
• The min stack stores the running minimum at each depth: min_stack[i] = min(val[i], min_stack[i-1])
• Always pop from BOTH stacks on pop()—they must stay synchronised
• The empty min stack edge case on first push must be handled: push val directly when the min stack is empty
• This pattern (augmenting with a parallel tracking structure) generalises to sliding window max/min, LRU cache, and stack-based histogram problems
• The space cost is O(N) auxiliary; the single-stack approach with encoded pairs reduces this but risks overflow
• LeetCode 155 is the canonical version; variants include Min Queue, Max Stack, and Stack with Middle element