Min Stack: tracking the minimum without scanning it

The problem statement is short. Design a stack where push, pop, top, and getMin all run in O(1). The first three are trivial — any stack does them in constant time. getMin is the hard part. Without any extra bookkeeping, computing the minimum requires a full scan of every element currently on the stack, which is O(n). The constraint forces you to maintain the minimum incrementally, never recomputing it from scratch.

The problem

Design a MinStack class that supports push, pop, top, and getMin — where every operation, including retrieving the minimum element currently in the stack, must run in O(1) time. Full statement: LeetCode 155.

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

What the constraint O(1) actually demands

The value range is -2^31 <= val <= 2^31 - 1 — the full 32-bit integer range, including INT_MIN. That matters. Any approach that tries to encode "no minimum" as a sentinel value like Integer.MAX_VALUE is dangerous; a legitimate push of INT_MAX would clobber that sentinel. The correct answer is to track whether the minimum-tracking structure is empty separately from what value it holds.

At most 3 * 10^4 calls will be made. That is small enough that an O(n) getMin would run in well under a second in isolation. But the problem explicitly mandates O(1) for each operation — this is a design problem, and the efficiency requirement is the constraint to satisfy, not a hint to optimize a working solution. A brute-force scan does not satisfy the requirement; it answers it wrong.

The problem also guarantees that pop, top, and getMin are only called on a non-empty stack. That removes one family of defensive checks from the implementation. You do not need to handle the empty-stack case for reads.

Approach 1: brute force — scan on every getMin

The naivest reading is: keep a plain list, and whenever getMin is called, walk the whole list and find the answer.

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

public class MinStack {
    private List<int> stack = new List<int>();
 
    public MinStack() { }
 
    public void Push(int val) {
        stack.Add(val);
    }
 
    public void Pop() {
        stack.RemoveAt(stack.Count - 1);
    }
 
    public int Top() {
        return stack[stack.Count - 1];
    }
 
    public int GetMin() {
        int m = stack[0];
        for (int i = 1; i < stack.Count; i++)
            if (stack[i] < m) m = stack[i];
        return m;
    }
}

This is correct. It is also disqualified by the requirement. getMin is O(n) — every call walks every element currently on the stack. The other three operations are O(1).

The lesson from the brute force is what information you are missing: at the moment you call getMin, you need the answer ready, not deferred. That means the minimum must be tracked as elements arrive and depart, not computed when asked.

Complexity: push/pop/top O(1); getMin O(n). Space O(n).

Approach 2: two stacks — keep a parallel minimum history

The core observation is that the minimum of the stack changes only on push (it can decrease) and pop (it can increase if you remove the current minimum). Crucially, the minimum after a pop is exactly what the minimum was before the corresponding push. That is a history. A stack is a natural container for a history that unwinds in LIFO order.

So: maintain a second stack — call it min_stack — where the top always holds the current minimum. On push(val), if val is less than or equal to the current minimum, push it onto min_stack too. On pop, if the value being removed equals the current minimum, pop min_stack as well.

The <= is load-bearing. If you push 5, 1, 1 and use strict <, only one 1 lands in min_stack. Then you pop the top 1 from the main stack, the code sees it equals min_stack[-1] and pops min_stack — but now min_stack is empty, even though a second 1 still exists in the main stack. Using <= means duplicate minimums each get their own slot in min_stack, so every pop that removes a copy of the minimum correctly removes one corresponding copy from min_stack.

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

Step by step:

• push(-2): main_stack becomes [-2]. min_stack is empty, so push unconditionally -> [-2].
• push(0): main_stack [-2, 0]. 0 > -2, so skip min_stack. It stays [-2].
• push(-3): main_stack [-2, 0, -3]. -3 <= -2, so push -> min_stack is [-2, -3].
• getMin(): return min_stack[-1] = -3. Correct.
• pop(): popped value is -3. It equals min_stack[-1] = -3, so pop min_stack too. Now main_stack is [-2, 0], min_stack is [-2].
• top(): return main_stack[-1] = 0. Correct.
• getMin(): return min_stack[-1] = -2. Correct.

Every operation touches only the top of a stack. Constant time in all cases.

class MinStack:
    def __init__(self):
        self.main_stack = []
        self.min_stack = []
 
    def push(self, val: int) -> None:
        self.main_stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
 
    def pop(self) -> None:
        popped = self.main_stack.pop()
        if popped == self.min_stack[-1]:
            self.min_stack.pop()
 
    def top(self) -> int:
        return self.main_stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]

public class MinStack {
    private Stack<int> mainStack = new Stack<int>();
    private Stack<int> minStack = new Stack<int>();
 
    public MinStack() { }
 
    public void Push(int val) {
        mainStack.Push(val);
        if (minStack.Count == 0 || val <= minStack.Peek())
            minStack.Push(val);
    }
 
    public void Pop() {
        int popped = mainStack.Pop();
        if (popped == minStack.Peek())
            minStack.Pop();
    }
 
    public int Top() {
        return mainStack.Peek();
    }
 
    public int GetMin() {
        return minStack.Peek();
    }
}

Complexity: All operations O(1). Space O(n) in the worst case — a strictly decreasing sequence like 5, 4, 3, 2, 1 pushes every element into both stacks. In an average mixed workload, min_stack is considerably smaller than main_stack.

Approach 3: single stack with (value, current-min) pairs

There is another way to attach the minimum to each element: store it directly alongside the value. Instead of a plain integer, each stack slot holds a pair (val, min_at_this_moment). When you push, you compute the new minimum immediately and bake it into the pair. When you pop, the pair disappears entirely — no synchronization logic between two structures needed.

class MinStack:
    def __init__(self):
        self.stack = []
 
    def push(self, val: int) -> None:
        current_min = val if not self.stack else 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]

public class MinStack {
    private Stack<(int val, int min)> stack = new Stack<(int, int)>();
 
    public MinStack() { }
 
    public void Push(int val) {
        int currentMin = stack.Count == 0 ? val : Math.Min(val, stack.Peek().min);
        stack.Push((val, currentMin));
    }
 
    public void Pop() {
        stack.Pop();
    }
 
    public int Top() {
        return stack.Peek().val;
    }
 
    public int GetMin() {
        return stack.Peek().min;
    }
}

Trace through the same example: push(-2) stores (-2, -2); push(0) stores (0, -2) because the running minimum is still -2; push(-3) stores (-3, -3) because -3 is now the new minimum. After pop() removes the top pair (-3, -3), the new top is (0, -2) and getMin() correctly returns -2. No separate structure, no cross-stack synchronization — the minimum at every historical stack state is recorded inside each node.

Complexity: All operations O(1). Space O(n), but every element now takes twice the memory of the brute-force approach. A stack of 30,000 pairs costs about 480 KB at 8 bytes per int pair — negligible in practice, but the constant factor is higher than either the plain stack (approach 1) or a sparse min_stack (approach 2 when the minimum rarely changes).

Edge cases in detail

Duplicate minimum values. Push 1, 2, 1. After all three pushes, min_stack in approach 2 is [1, 1]. Pop the top 1: min_stack also pops one 1, leaving [1]. getMin() correctly returns 1. If you had used strict < rather than <=, only one 1 would have been pushed into min_stack, and the first pop would empty it — wrong. In approach 3, each pair carries its own snapshot, so this is never an issue regardless.

Single element. Push 7, then call getMin(), then pop(). In approach 2, pushing puts 7 in both stacks. getMin() returns 7. Popping removes 7 from both. In approach 3, the only pair is (7, 7). Both handle this cleanly.

Strictly decreasing sequence. Push 5, 4, 3, 2, 1. In approach 2, every push satisfies val <= min_stack[-1], so min_stack grows to the same size as main_stack. Worst-case space for approach 2 is no better than approach 3 in this scenario — both are O(n) pairs' worth of data.

All equal values. Push 3, 3, 3. In approach 2, min_stack is [3, 3, 3] (because 3 <= 3 triggers the push each time). Pop once: removes one 3 from both. getMin() = 3. Pop again: same. Correct all the way down.

Overflow boundary. Values can be -2^31. Python handles arbitrary integers natively. In C#, comparing int values directly is safe throughout the full range — there is no arithmetic that could overflow here since we are only doing comparisons, not additions.

Which one to ship

I reach for approach 3 (pairs) in an interview setting. Here is why.

Approach 2 (two stacks) is elegant and well-known, but it has one subtle invariant to maintain: the synchronization between main_stack and min_stack on pop. You have to remember that <= is required (not <), and that the pop synchronization is triggered by value equality, not by position. That is two non-obvious implementation decisions. Under interview pressure, the place people make mistakes here is the pop logic — specifically forgetting to sync min_stack when the minimum is removed.

Approach 3 buries the logic entirely inside push. Once you write current_min = min(val, stack[-1][1]) if stack else val, there is nothing left to get wrong. pop, top, and getMin are all single-line index operations. You can verify correctness by inspection: each pair is a snapshot; popping restores the previous snapshot automatically.

The downside is memory. In approach 2, if you push a million elements that are all increasing, min_stack stays at size 1 while main_stack grows to a million. In approach 3, every element carries a min field regardless. For the problem's 3 * 10^4 constraint this does not matter. For a production implementation sitting under a high-frequency trading system that pushes millions of prices per second, approach 2's space savings become real.

In a production code review I would accept either. The difference is small enough that I would not push back on approach 2 in a review — I would just note the duplicate-minimum invariant in a comment.

Comparison table

The underlying pattern: auxiliary state that tracks aggregate queries

The mental model here extends well beyond this one problem. Whenever you have a dynamic container (stack, queue, deque) and need to answer an aggregate query (minimum, maximum, sum, running median) in O(1), the trick is to maintain a secondary structure that shadows the primary one. The secondary structure updates incrementally on insert and remove — it is never recomputed from scratch.

For stacks specifically, the min_stack pattern generalizes directly to a max_stack (flip the comparison), and with more bookkeeping to a structure that supports both getMin and getMax simultaneously. For queues, the same idea appears in "Sliding Window Maximum" (LeetCode 239), but a monotonic deque replaces the simple stack because queue removal happens at the front, not the back.

Where this sits in the stack series

This is problem three in the series, after Valid Parentheses (20) and Evaluate Reverse Polish Notation (150). Those two established stack as a structure for tracking "last seen" context and for evaluating expressions left-to-right. Min Stack is different in character: it is a design problem rather than an algorithmic one. The challenge is not finding a clever traversal — it is designing a data structure that satisfies a performance contract.

Max Stack (LeetCode 716) is the direct extension. Like Min Stack, but you also need popMax() — remove the maximum element wherever it sits in the stack. That is harder because the maximum might not be on top, which breaks the simple min_stack approach. It requires an ordered set alongside the stack.

Implement Queue using Stacks (LeetCode 232) is another design problem: achieve FIFO semantics using only LIFO primitives. The transfer trick (two stacks, one for push and one for pop) is the same flavor of "use an auxiliary structure to restructure access order."

Sliding Window Maximum (LeetCode 239) takes the min-tracking idea into a different container shape. You have a sliding window of size k over an array and need the maximum of each window in O(n) total. The monotonic deque is the equivalent of min_stack, but adapted for an expiring window rather than a LIFO structure.

Maximum Frequency Stack (LeetCode 895) is the most complex neighbor: pop returns the most frequently pushed element, with ties broken by recency. It requires a frequency map and a stack-per-frequency — a more elaborate version of the "track aggregate state alongside the data" pattern.