Min Stack

A min stack is an ordinary Stack augmented so that, in addition to the usual push, pop, and top (each O(1)), it can answer getMin() — the smallest element currently in the stack — also in O(1) time. The naïve approach of scanning the stack on every getMin() is O(n); the trick is to store some redundant state alongside the stack so the minimum is always one pointer-dereference away. There are two clean implementations and one memory-optimized variant. The structure shows up under LeetCode 155 (Min Stack) and is the canonical “augmented data structure” interview question — the lesson it teaches (carry the answer with the data, don’t recompute it) generalizes to the Monotonic Stack, Monotonic Deque, and the running-minimum sliding-window pattern.

1. Intuition — The Hotel Front Desk’s Cheapest-Room Tracker

Imagine a hotel where guests check in (push) and check out (pop) in strict reverse order — the most recent arrival is the next to leave. The receptionist must answer one extra question instantly at any moment: what is the cheapest occupied room right now? The naïve method — walk the guest registry and find the smallest price — is too slow when guests come and go thousands of times a minute.

A clever receptionist keeps a second list: every time a guest arrives, the receptionist asks “is this guest’s room cheaper than my current cheapest?” If yes, write the new price at the top of the second list. If no, write down the same current cheapest again. The second list grows in lockstep with the registry — one entry per guest. When a guest checks out, both lists shrink by one. The cheapest occupied price is always whatever sits at the top of the second list, fetched in O(1).

That second list is a running-minimum stack. The reason it works is that the stack discipline is LIFO (Last In, First Out): the moment we pop a guest, we restore the exact state from before that guest arrived — including the previous cheapest. So we don’t need to recompute the minimum on pop; we just look at what was the minimum right before this guest arrived, which is conveniently sitting at the new top of the second list.

The deep idea generalizes: for any associative monotone aggregate (min, max, gcd, sum) over a stack, you can maintain that aggregate in O(1) per operation by storing it alongside each frame. Sum is trivial (running total). Min and max work by storing the running min/max. GCD works because gcd is associative. The trick fails for non-associative or non-undoable aggregates (e.g., median).

2. Tiny Worked Example

We’ll use Implementation A (auxiliary “min-so-far” stack) on the operation sequence:

push 5, push 2, push 7, push 2, push 1, pop, getMin, pop, getMin

Step	Op	main stack	min stack	getMin
0	start	[]	[]	—
1	push 5	[5]	[5]	—
2	push 2	[5, 2]	[5, 2]	—
3	push 7	[5, 2, 7]	[5, 2, 2]	—
4	push 2	[5, 2, 7, 2]	[5, 2, 2, 2]	—
5	push 1	[5, 2, 7, 2, 1]	[5, 2, 2, 2, 1]	—
6	pop → 1	[5, 2, 7, 2]	[5, 2, 2, 2]	—
7	getMin	(no change)	(no change)	2
8	pop → 2	[5, 2, 7]	[5, 2, 2]	—
9	getMin	(no change)	(no change)	2

The right column reads getMin = 2 after the first pop because 1 left and 2 was the previous minimum, which is now at the top of the min stack. The min stack mirrors the main stack in length: every push to one is a push to the other, every pop from one is a pop from the other. That lockstep is what makes both operations true O(1) (no scanning, no conditionals beyond a single comparison).

The line push 7 → min stack [5, 2, 2] is the crucial one: even though 7 is not itself the new minimum, we still push the current minimum (2) onto the auxiliary stack. This way, when 7 is popped, the auxiliary top is still 2 — no recomputation needed.

3. Pseudocode

3.1 Implementation A — Auxiliary “Min-So-Far” Stack (Lockstep)

class MinStack:
    main:    Stack of values
    min_aux: Stack of running minima       # same length as main at all times

    push(x):
        main.push(x)
        if min_aux.is_empty():
            min_aux.push(x)
        else:
            min_aux.push( min(x, min_aux.top()) )

    pop():
        min_aux.pop()
        return main.pop()

    top():
        return main.top()

    get_min():
        return min_aux.top()                # always the min of all elements in main

Every operation is one or two stack ops on plain stacks: O(1) worst-case (assuming an array-backed stack with amortized O(1) pushes — see Stack for that argument).

3.2 Implementation B — Single Stack of (value, current_min) Tuples

class MinStack:
    stack: Stack of pairs (value, running_min)

    push(x):
        if stack.is_empty():
            stack.push( (x, x) )
        else:
            cur_min := stack.top().running_min
            stack.push( (x, min(x, cur_min)) )

    pop():
        return stack.pop().value

    top():
        return stack.top().value

    get_min():
        return stack.top().running_min

Functionally equivalent to A — the running minimum still travels with each frame. The difference is one stack instead of two; tuple allocation per push instead of two scalar pushes. In Python, tuple-per-push has noticeable overhead; in C++ with a struct {int val, min;} it’s free. Pick whichever your language makes ergonomic.

3.3 Implementation C — Memory-Optimized: Push to Aux Only on New Minimum

The lockstep approach (A) wastes space when many consecutive elements are not new minima. Implementation C only pushes to the auxiliary stack when the new element is a new minimum (using ≤ rather than < to handle duplicates correctly):

class MinStack:
    main:    Stack of values
    min_aux: Stack of "checkpoint minima"

    push(x):
        main.push(x)
        if min_aux.is_empty() or x <= min_aux.top():     # ≤ matters; see Pitfall 9.1
            min_aux.push(x)

    pop():
        x := main.pop()
        if x == min_aux.top():
            min_aux.pop()
        return x

    get_min():
        return min_aux.top()

Now min_aux shrinks in size proportional to the number of new minima the input has seen — roughly O(log n) for random data, O(1) for monotonically increasing input, O(n) worst-case for monotonically decreasing input. The ≤ (not <) on push is essential: if duplicates of the current minimum aren’t recorded, the first pop of one will incorrectly clear the auxiliary entry while the duplicate is still in main.

4. Python Implementation

A reference implementation matching the LeetCode 155 contract — push(val), pop(), top(), getMin(), all O(1):

4.1 Implementation A — Auxiliary Stack (Clearest)

class MinStack:
    """Stack supporting push, pop, top, and getMin all in O(1) time.
 
    Uses two parallel stacks. `_main` holds the actual values; `_min_so_far`
    holds, at each level, the minimum of all values *at or below* that level
    in `_main`. Thus `_min_so_far[-1]` is always the global minimum.
    """
 
    def __init__(self) -> None:
        self._main: list[int] = []
        self._min_so_far: list[int] = []
 
    def push(self, val: int) -> None:
        self._main.append(val)
        if not self._min_so_far:
            self._min_so_far.append(val)
        else:
            # Push the smaller of (incoming val, current running min).
            # This keeps the two stacks in lockstep — crucial for pop().
            self._min_so_far.append(min(val, self._min_so_far[-1]))
 
    def pop(self) -> int:
        # Pop both stacks together so the running-min invariant is preserved.
        self._min_so_far.pop()
        return self._main.pop()
 
    def top(self) -> int:
        return self._main[-1]
 
    def getMin(self) -> int:                                # noqa: N802 (LC API)
        return self._min_so_far[-1]

4.2 Implementation C — Memory-Optimized

class MinStackOptimized:
    """O(1) min stack with auxiliary growth proportional to the number of
    distinct running minima — much smaller than `n` on random inputs.
 
    Crucially uses `<=` (not `<`) when deciding whether to record a new
    minimum, so that duplicates of the current minimum are tracked
    individually. See Pitfall 9.1 for the why.
    """
 
    def __init__(self) -> None:
        self._main: list[int] = []
        self._min_aux: list[int] = []
 
    def push(self, val: int) -> None:
        self._main.append(val)
        if not self._min_aux or val <= self._min_aux[-1]:
            self._min_aux.append(val)
 
    def pop(self) -> int:
        val = self._main.pop()
        # Only pop the aux when the value being removed *was* the running min.
        if val == self._min_aux[-1]:
            self._min_aux.pop()
        return val
 
    def top(self) -> int:
        return self._main[-1]
 
    def getMin(self) -> int:                                # noqa: N802
        return self._min_aux[-1]

The two implementations expose the space-vs-clarity trade-off: A is one extra value per push (always 2× memory of the underlying stack); C is variable (often <2× and sometimes ≪2×) but with a less obvious invariant.

4.3 Quick Sanity Test

def _demo() -> None:
    s = MinStack()
    for x in [5, 2, 7, 2, 1]:
        s.push(x)
    assert s.getMin() == 1
    s.pop()
    assert s.getMin() == 2
    s.pop()
    assert s.getMin() == 2
    s.pop()
    assert s.getMin() == 2
    s.pop()
    assert s.getMin() == 5
 
if __name__ == "__main__":
    _demo()

5. Complexity

Operation	Time	Space (Impl A)	Space (Impl C, worst)	Space (Impl C, average random)
push	O(1)	+1	+1 (only on new min)	+1 with prob ≈ 1/k at step k
pop	O(1)	−1	−0 or −1	−1 with same prob
top	O(1)	0	0	0
getMin	O(1)	0	0	0
Total	O(n) ops in O(n) time	2n cells	up to 2n cells	≈ n (1 + Hₙ) where Hₙ ≈ ln n

Why Implementation C averages logarithmic auxiliary space on random inputs. A new element is a new minimum at step k with probability 1/k (each of the first k elements is equally likely to be the smallest; this is the classic “records in a random sequence” result — see Knuth, TAoCP Vol. 3, §5.1.1). Summing across n pushes gives an expected count of new minima equal to the harmonic number H_n = 1 + 1/2 + 1/3 + ... + 1/n ≈ ln(n) + γ (Wikipedia: Harmonic number). So on average random inputs, the auxiliary stack size is O(log n) — a dramatic saving for long sessions.

Worst case for Implementation C. A monotonically decreasing sequence pushes a new minimum at every step, so the auxiliary stack grows in lockstep with main, restoring the same 2n-cell footprint as A. There is no input where C uses more space than A.

Why no implementation can do better than O(n) total. Any min-stack implementation must remember at least which past minima were “current” at each level, because a pop followed by getMin must recover the prior minimum without seeing the popped element again. An adversary that pushes a strictly decreasing sequence forces the implementation to record n distinct values, lower-bounding total space by Ω(n).

6. Variants

6.1 Max Stack (LeetCode 716)

Max stack is the symmetric problem — getMax() in O(1). Implementation: identical to min stack with < replaced by > (and ≤ by ≥ in the optimized version). LeetCode 716 also asks for popMax() (remove and return the maximum, even if it’s not on top), which breaks the LIFO discipline and is not solvable in O(1) by augmentation alone — it typically uses a doubly linked list plus a balanced BST to support O(log n) per op.

6.2 Min Deque

A double-ended queue with O(1) min on either end requires a Monotonic Deque underneath — the same trick used for “sliding window minimum” (LeetCode 239). The reason a deque is harder than a stack is that on a deque, both ends can be popped; the auxiliary structure must track minima reachable from either side. The standard solution is a single deque holding only “potentially-still-min” candidates in monotonically increasing order from front to back; whenever a new value is pushed at the back, all rear-end candidates ≥ the new value are popped (they can no longer be the min if the new value is in scope). The min is always at the front.

6.3 Min Queue

A FIFO queue with O(1) min. Solvable by two min stacks — the same trick used in Queue from Two Stacks applied to min-augmented stacks. The amortized analysis is also the same: each element is pushed/popped on each underlying stack at most twice across its lifetime.

6.4 K-th Smallest in Stack

Generalizing to “kth smallest in O(1)” is not solvable by simple augmentation — it requires a Skip List or Red-Black Tree backing for O(log n) updates. See the literature on order statistics trees.

6.5 Min Stack with Negative Encoding (LeetCode constraint trick)

Some sources show a “single stack” trick that stores 2 * x - current_min whenever x is a new minimum, decoding on pop. This saves space but introduces overflow and signed-arithmetic hazards (2 * x can overflow int64 if x is near the bounds). It is a clever party trick — not recommended for production code or interviews unless the constraints make it justified.

7. Use Cases

The min stack is rarely a load-bearing component of large systems on its own; its real significance is pedagogical. The pattern it teaches — maintain a redundant aggregate alongside the primary structure so queries are constant-time — appears throughout systems and algorithm design:

• Range-minimum queries on streams with stack-discipline access patterns (parser state stacks, expression evaluators).
• Histogram-largest-rectangle style problems (LeetCode 84) lean on a Monotonic Stack, which is ideologically the same idea: store running aggregates alongside the data so a query never scans the past.
• DP with stack-based state: when a stack of partial solutions also needs the current best, a min-stack-style augmentation supports O(1) “what’s the best so far” queries.
• Undo/redo with cost tracking: text editors that show “current line count” or “smallest character used so far” can maintain those aggregates as min/max-stack frames piggybacking on the undo stack.

8. Diagram — Two Implementations Side by Side

flowchart LR
    subgraph A["Impl A: Lockstep auxiliary"]
        A1["main: 5 2 7 2 1"]
        A2["min:  5 2 2 2 1"]
    end
    subgraph C["Impl C: Push only on new min"]
        C1["main:    5 2 7 2 1"]
        C2["min_aux:    5 2 2 1"]
    end

What this diagram shows. Two horizontal layouts comparing the auxiliary structures of Implementation A and Implementation C after the same sequence of pushes (5, 2, 7, 2, 1). Both expose the running minimum at the top in O(1). Implementation A’s auxiliary stack is exactly as long as the main stack (5 entries). Implementation C’s is shorter (4 entries) because 7 was not a new minimum, so nothing was pushed on its arrival. The duplicate 2 was recorded (because the optimized algorithm uses ≤, not <); skipping it would create a bug — see Pitfall 9.1.

The takeaway: both implementations satisfy the same external contract (push, pop, top, getMin all O(1)). They differ in space — A always uses 2n cells; C uses fewer on inputs that aren’t monotonically decreasing.

9. Pitfalls

1. < vs ≤ on duplicates in Implementation C. If you push the current minimum a second time and use strict less-than to decide whether to record it, the auxiliary stack will not see the duplicate. When you later pop the duplicate, you’ll incorrectly remove the auxiliary entry (because val == min_aux[-1]) — and getMin on the still-present original returns the wrong (old) minimum or crashes. Always use ≤ on push and == on pop. This single character is a famous LeetCode 155 bug.
2. Not popping both stacks in Implementation A. Forgetting to pop _min_so_far alongside _main desyncs the two stacks; getMin then returns stale minima from levels that no longer exist. The lockstep invariant is only as strong as the discipline enforcing it.
3. Re-computing the min on getMin “just to be safe.” Some candidates do this to “double-check” — and turn an O(1) operation into O(n), defeating the purpose. The whole point of the structure is that the answer is already cached; trust the invariant.
4. Forgetting the operation contract is undefined on empty stack. pop, top, getMin on an empty min stack are usually unspecified by the problem; production code should raise an exception or sentinel. LeetCode’s problem statement guarantees the test cases never call these on empty, so the boilerplate is omitted in submissions — don’t skip it elsewhere.
5. Storing references in mutable types. If the stack holds objects whose comparison key can change (e.g., a list whose first element you later mutate), the running-minimum invariant breaks silently. The structure assumes the values are immutable for the lifetime they’re in the stack — this is the same caveat that applies to Hash Table keys.
6. Mixing up the invariant when extending to max. When converting min stack to max stack, every comparison flips: min → max, < → >, ≤ → ≥. It is easy to flip one but not all, especially with the optimized variant. Write tests with monotonically-increasing AND monotonically-decreasing AND constant-value inputs.
7. The 2*x - current_min encoding trick has overflow risk. If x is near INT_MIN, 2*x underflows; even 2*x - current_min can wrap silently in C/C++. Languages with arbitrary precision (Python) are immune, but the trick still saves only O(n) space at the cost of clarity — usually a bad trade.
8. Confusing top() with getMin(). They are different: top() returns the most-recently-pushed value (LIFO order); getMin() returns the smallest value currently in the stack regardless of when it was pushed. Some bug reports trace to a sleepy top where getMin was meant.
9. Interview pitfall — claiming the single stack with 2x - min encoding is “the most efficient.” It saves space but doesn’t improve time, and it adds bugs. Interviewers reward the clearer lockstep solution unless they specifically ask for the encoded variant — and in that case, narrate the overflow caveat.

10. Diagram — Lockstep Push and Pop Animation

sequenceDiagram
    participant U as User
    participant M as main stack
    participant A as min_aux stack
    U->>M: push 5
    U->>A: push 5
    Note right of A: min = 5
    U->>M: push 2
    U->>A: push min(2, 5) = 2
    Note right of A: min = 2
    U->>M: push 7
    U->>A: push min(7, 2) = 2
    Note right of A: min = 2
    U->>M: pop → 7
    U->>A: pop
    Note right of A: min = 2
    U->>M: pop → 2
    U->>A: pop
    Note right of A: min = 5

What this diagram shows. A swimlane sequence diagram where each row is a sequential operation; arrows from User to main stack and min_aux stack happen in lockstep on every push and every pop. The “Note” callouts show the value of getMin() at each point. Two crucial facts emerge: (1) every user-level operation maps to exactly two underlying stack operations, so the per-op cost remains O(1); (2) the value being pushed onto min_aux is min(incoming, current_min), not the incoming value alone — that’s the redundancy that lets pop recover the previous minimum without recomputation.

11. Common Interview Problems

#	Problem	Min Stack’s Role
LC 155	Min Stack	The canonical problem — design from scratch
LC 716	Max Stack	Symmetric problem; popMax requires a balanced BST or DLL+heap
LC 1381	Design a Stack with Increment Operation	Augment with running deltas — cousin pattern
LC 232	Implement Queue using Stacks	Same “augment a stack” mindset; see Queue from Two Stacks
LC 84	Largest Rectangle in Histogram	Monotonic Stack — same redundancy idea, different invariant
LC 239	Sliding Window Maximum	Monotonic Deque — extension of the pattern to deques
LC 901	Online Stock Span	Augmented stack of (price, days_since) — same family
LC 895	Maximum Frequency Stack	Augmented stack indexed by frequency buckets — generalization

12. Open Questions

• Is there a workload where Implementation C’s variable-size auxiliary stack beats A on real hardware? In micro-benchmarks, the branch on every push (if val <= aux[-1]) sometimes costs more than the unconditional second push of A; the answer depends on branch predictor behavior and input distribution.
• Can the 2x - min encoding be made overflow-safe with checked arithmetic without losing the space benefit? In Rust with checked_mul / checked_sub it works, but every operation pays a branch; in C++ you’d need 128-bit intermediate.
• What’s the “right” data structure for “k-th smallest in a stack with O(log n) per op”? An order-statistic Red-Black Tree indexed by value works but doesn’t respect LIFO discipline on its own — you’d also need a stack of insertion order to know which node to remove on pop.
• Beyond min and max, what aggregates admit O(1) augmentation on a stack? The condition seems to be “the aggregate has an inverse element” or “the aggregate is associative and idempotent” — but the precise characterization deserves a clean writeup. Sum (with subtraction on pop) and XOR work; product breaks if elements can be zero.

13. See Also

• Stack — the underlying data structure; covers backing implementations and amortized push complexity
• Monotonic Stack — generalizes the running-minimum trick to “running monotone subsequence” for next-greater/smaller problems
• Monotonic Deque — the deque counterpart; powers sliding-window min/max
• Queue — symmetric ordering discipline; together with stacks underlies Queue from Two Stacks and Stack from Two Queues
• Queue from Two Stacks — applies a similar “carry the answer” pattern to convert one ADT into another
• Amortized Analysis — formal framework for the average-cost arguments used here (planned)
• Big-O Notation
• SWE Interview Preparation MOC