Min Stack: O(1) Minimum Retrieval

Key Insights

• Maintaining an auxiliary stack that tracks the minimum at each state enables O(1) minimum retrieval without sacrificing the O(1) guarantees of standard stack operations.
• The fundamental insight is that each stack position has a deterministic “minimum so far” that only changes when elements are pushed or popped—making it perfectly suited for stack-based tracking.
• This pattern of “tracking state at each level” extends beyond minimums to maximums, frequencies, and other aggregate values, making it a foundational technique for stack-based algorithm design.

The Problem: Why Naive Approaches Fail

The Min Stack problem appears deceptively simple: design a stack that supports push, pop, top, and getMin—all in O(1) time. Standard stacks already give us the first three operations in constant time. The challenge lies entirely in that fourth operation.

Your first instinct might be to track a single min variable. Push is easy—compare and update. But what happens when you pop the current minimum? You’d need to scan the entire stack to find the new minimum, degrading pop to O(n). That violates the requirement.

Another naive approach: sort the elements or maintain a heap alongside the stack. Heaps give O(log n) minimum retrieval, but that’s not O(1). We need something smarter.

The constraint that makes this problem interesting is that we need O(1) time for all operations simultaneously. This forces us to think about what information we can precompute and store.

The Key Insight: Auxiliary Stack

Here’s the breakthrough: at any given moment, the minimum element in the stack is deterministic. It depends only on what elements are currently in the stack. More importantly, when we push a new element, the new minimum is simply min(current_min, new_value). When we pop, the minimum reverts to whatever it was before that push.

This temporal property—that the minimum at each stack state is independent and reversible—means we can track it with another stack. For every element in our main stack, we store the corresponding minimum in an auxiliary stack.

class MinStack:
    def __init__(self):
        self.stack = []      # Main stack for values
        self.min_stack = []  # Auxiliary stack for minimums

The two stacks stay synchronized: same size, same push/pop rhythm. The top of min_stack always holds the minimum of all elements currently in stack.

Why does this work? Consider the stack as a timeline. Each push creates a new “state” with its own minimum. Each pop reverts to the previous state. The auxiliary stack is essentially a history of minimum values across all states.

Implementation Walkthrough

Let’s implement each operation with careful attention to edge cases.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    
    def push(self, val: int) -> None:
        self.stack.append(val)
        # If min_stack is empty, val is the minimum
        # Otherwise, compare with current minimum
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))
    
    def pop(self) -> None:
        # Pop from both stacks to maintain synchronization
        self.stack.pop()
        self.min_stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_stack[-1]

Push operation: We always push to both stacks. The value pushed to min_stack is the minimum between the new value and the current minimum (top of min_stack). This maintains our invariant.

Pop operation: We pop from both stacks. This is crucial—the stacks must stay synchronized. After popping, min_stack[-1] correctly reflects the minimum of the remaining elements.

Edge cases to consider:

1. Empty stack: The problem typically guarantees operations are valid, but defensive code would check before pop, top, or getMin.

2. Duplicate minimums: This implementation handles duplicates correctly. If we push 1, 1, 1, our min_stack contains 1, 1, 1. Popping removes one 1 from each stack, and the minimum remains 1.

Here’s the equivalent Java implementation:

class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;
    
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

Space Optimization: Single Stack Approach

The two-stack approach uses O(2n) = O(n) space. We can achieve the same result with a single stack by storing tuples of (value, current_min):

class MinStackOptimized:
    def __init__(self):
        self.stack = []  # Stores (value, min_at_this_level) tuples
    
    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = min(val, self.stack[-1][1])
            self.stack.append((val, current_min))
    
    def pop(self) -> None:
        self.stack.pop()
    
    def top(self) -> int:
        return self.stack[-1][0]
    
    def getMin(self) -> int:
        return self.stack[-1][1]

Trade-offs between approaches:

In practice, the single-stack approach has slightly better cache locality since all data lives in one contiguous array. However, the difference is negligible for most applications. Choose based on what’s clearer in your codebase.

Visual Trace & Complexity Analysis

Let’s trace through a sequence of operations to solidify understanding:

Operations: push(3), push(1), push(2), getMin(), pop(), getMin()

After push(3):
  stack:     [3]
  min_stack: [3]
  
After push(1):
  stack:     [3, 1]
  min_stack: [3, 1]    ← 1 < 3, so new min is 1
  
After push(2):
  stack:     [3, 1, 2]
  min_stack: [3, 1, 1]  ← 2 > 1, so min stays 1
  
getMin() → returns 1 (top of min_stack)

After pop():
  stack:     [3, 1]
  min_stack: [3, 1]     ← removed the 2 and its corresponding min
  
getMin() → returns 1 (still the minimum)

Complexity Analysis:

• Time Complexity: O(1) for all operations. Each operation performs a constant number of array accesses and comparisons.
• Space Complexity: O(n) where n is the number of elements in the stack. We store at most 2n values (n in each stack or n tuples).

The space overhead is the price we pay for O(1) getMin. There’s no free lunch—we’re trading space for time.

Variations & Extensions

The Min Stack pattern extends naturally to several related problems:

Max Stack: Identical approach, just track maximums instead. Replace min() with max().

Min Queue: This is trickier since queues are FIFO. The classic solution uses two stacks to simulate a queue, with each stack maintaining its own minimum. The amortized time for all operations remains O(1).

class MinQueue:
    def __init__(self):
        self.in_stack = MinStack()   # For enqueue
        self.out_stack = MinStack()  # For dequeue
    
    def enqueue(self, val):
        self.in_stack.push(val)
    
    def dequeue(self):
        if not self.out_stack.stack:
            while self.in_stack.stack:
                self.out_stack.push(self.in_stack.pop())
        return self.out_stack.pop()
    
    def get_min(self):
        if not self.in_stack.stack:
            return self.out_stack.getMin()
        if not self.out_stack.stack:
            return self.in_stack.getMin()
        return min(self.in_stack.getMin(), self.out_stack.getMin())

Real-world applications:

1. Sliding window minimum/maximum: Min Queue enables O(n) solutions for finding min/max in all windows of size k.

2. Undo systems: Each state can track aggregate information (like document word count) that’s instantly available without recalculation.

3. Expression evaluation: Tracking minimum precedence in operator stacks for optimized parsing.

4. Stock span problems: Tracking price relationships across historical data.

Summary

The Min Stack problem teaches a fundamental technique: tracking state at each level of a stack. Instead of recomputing aggregate values on demand, we maintain them incrementally as the stack evolves.

This pattern works because stacks have a beautiful property—they’re reversible. Every push can be undone by a pop, and the state reverts exactly. By storing the minimum (or any aggregate) at each level, we create a perfect history that requires no reconstruction.

When you encounter stack problems asking for O(1) access to aggregate information, reach for this auxiliary tracking pattern. It’s the difference between a brute-force O(n) scan and an elegant constant-time lookup.