Min/Max Stack

You are asked to design a stack that supports the usual push, pop, and top operations, but also a getMin that returns the current minimum element, and every single operation must run in $O(1)$ time. This is LeetCode 155 (Min Stack), and it appears constantly in interviews because the naive approach has a subtle flaw that reveals whether you truly understand how stacks work.

Why a Simple Variable Fails

Your first instinct might be to keep a single variable, current_min, updated on every push. When a new value is smaller, you overwrite current_min. Easy enough, until you pop. If the element you just removed was the current minimum, what is the new minimum? You have no record of it. You would have to scan the entire stack to find out, which destroys the $O(1)$ guarantee.

The problem is that a single variable forgets the history. A stack is a time-travel data structure: every pop rewinds the state by one step. Your minimum tracking needs to rewind too.

The Solution: Store Pairs

The fix is elegant. Instead of storing bare values, store a pair (value, current_min) at every position. When you push a new element, compute the new minimum as min(value, previous_min) and tuck it right alongside the value. Now every entry in the stack knows what the minimum was at the moment it was pushed. When you pop, the previous entry still carries the correct minimum for its point in time. No scanning required.

Walking Through a Sequence

Let us trace through a series of operations to see the pairs in action.

push(5): The stack is empty, so the minimum is 5 itself. Stack: [(5, 5)].

push(3): The new minimum is min(3, 5) = 3. Stack: [(5, 5), (3, 3)].

push(7): The new minimum is min(7, 3) = 3. Stack: [(5, 5), (3, 3), (7, 3)].

getMin(): We peek at the top pair, (7, 3), and return the second element: 3.

pop(): We remove (7, 3). Stack: [(5, 5), (3, 3)].

getMin(): The top pair is (3, 3). The minimum is still 3, since the value 3 is still on the stack.

pop(): We remove (3, 3). Stack: [(5, 5)].

getMin(): The top pair is (5, 5). The minimum has correctly reverted to 5. No scanning, no recomputation, just reading a stored value.

Code: MinStack

class MinStack:
    def __init__(self):
        self.stack = []  # each entry is (value, current_min)

    def push(self, val: int) -> None:
        if self.stack:
            mn = min(val, self.stack[-1][1])
        else:
            mn = val
        self.stack.append((val, mn))

    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]

Every operation touches only the top of the stack, so each runs in $O(1)$ time. The space overhead is $O(n)$ because every element stores a companion minimum.

Space Optimization with an Auxiliary Min Stack

In the pair approach, we store a minimum value for every single element, even when the minimum has not changed. If you push a million elements and only the first one is the minimum, you store that same minimum a million times.

A cleaner alternative is to maintain a separate auxiliary stack that only records new minimums. When you push a value that is less than or equal to the current minimum, push it onto the auxiliary stack as well. When you pop a value that equals the top of the auxiliary stack, pop the auxiliary stack too. The top of the auxiliary stack always holds the current minimum.

class MinStackOptimized:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

The worst case is still $O(n)$ space, as you can see by imagining pushing a strictly decreasing sequence, but in practice, when minimums are rare, the auxiliary stack stays small.

Supporting Both Min and Max

Some problems need both the minimum and maximum of the stack at all times. The extension is straightforward: store triples (value, current_min, current_max) instead of pairs.

class MinMaxStack:
    def __init__(self):
        self.stack = []  # (value, current_min, current_max)

    def push(self, val: int) -> None:
        if self.stack:
            mn = min(val, self.stack[-1][1])
            mx = max(val, self.stack[-1][2])
        else:
            mn = mx = val
        self.stack.append((val, mn, mx))

    def pop(self) -> None:
        self.stack.pop()

    def getMin(self) -> int:
        return self.stack[-1][1]

    def getMax(self) -> int:
        return self.stack[-1][2]

This is still $O(1)$ per operation. The trick works because both min and max are prefix-monotone: the minimum of the first k elements only depends on the minimum of the first k-1 elements and the kth element. The same holds for the maximum.

Max Stack with popMax: A Harder Problem

A harder variant is LeetCode 716, which asks for a Max Stack that supports popMax: remove and return the maximum element. This is fundamentally harder than getMin, because you now need to reach into the middle of the stack to extract an element, which breaks the LIFO contract.

With a regular min/max stack, getMin works in $O(1)$ because you never remove the minimum, you only report it. The moment you need to remove the extreme value, a plain stack cannot help you.

The standard approach uses a doubly linked list combined with a balanced BST (or sorted container) that maps values to nodes. The linked list preserves insertion order so you can still do push and pop. The BST lets you locate the maximum quickly. When you call popMax, the BST finds the node with the maximum value, and the doubly linked list removes it from its position. Both operations are $O(\log n)$. An alternative is a heap with lazy deletion, though that complicates pop operations.

Min Queue: A Queue with getMin

A queue is first-in, first-out, so tracking the minimum is not as natural as with a stack. But there is an elegant construction: simulate the queue using two min-stacks: an "input" stack and an "output" stack.

When you enqueue, push onto the input stack. When you dequeue, if the output stack is empty, pour everything from the input stack into the output stack (which reverses the order, giving FIFO behavior), then pop from the output stack. Each element moves between the two stacks at most once, so the amortized cost per operation is $O(1)$.

For getMin, simply return min(input_stack.getMin(), output_stack.getMin()), handling the case where either stack is empty. Since both stacks are min-stacks, each reports its minimum in $O(1)$, and the overall queue minimum is the smaller of the two.

class MinQueue:
    def __init__(self):
        self.in_stack = []   # (val, min)
        self.out_stack = []  # (val, min)

    def enqueue(self, val: int) -> None:
        mn = min(val, self.in_stack[-1][1]) if self.in_stack else val
        self.in_stack.append((val, mn))

    def dequeue(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                val = self.in_stack.pop()[0]
                mn = min(val, self.out_stack[-1][1]) if self.out_stack else val
                self.out_stack.append((val, mn))
        return self.out_stack.pop()[0]

    def getMin(self) -> int:
        if self.in_stack and self.out_stack:
            return min(self.in_stack[-1][1], self.out_stack[-1][1])
        if self.in_stack:
            return self.in_stack[-1][1]
        return self.out_stack[-1][1]

This two-stack queue trick is worth memorizing. It shows up not only in interview problems but also in streaming algorithms and amortized data structure design.

Complexity Analysis

For the basic MinStack (pair or auxiliary approach): push, pop, top, and getMin are all $O(1)$ time. Space is $O(n)$.

For the MinMaxStack with triples: same $O(1)$ time and $O(n)$ space.

For Max Stack with popMax: push, pop, top, getMax, and popMax all run in $O(\log n)$ time with the doubly linked list plus BST approach. Space is $O(n)$.

For the MinQueue: enqueue is $O(1)$, dequeue is $O(1)$ amortized, and getMin is $O(1)$. Space is $O(n)$.

The core takeaway across all these variations is the same: when you need to track an extreme value through a sequence of insertions and deletions, co-locate that information with the data itself. Every entry should remember the context it was born into, so that removing later entries automatically restores the earlier state.

Recognizing this pattern

You're probably looking at a min/max stack when:

• The problem says "design a data structure that supports push, pop, and getMin (or getMax) in O(1)."
• You need the running min or max of a LIFO sequence, where values come and go and you want the extreme of what's currently inside.
• Each operation must be constant time, ruling out re-scanning the stack.
• You want the same behavior for a queue: O(1) enqueue, dequeue, and getMin.

Common templates:

• Paired-value stack: each entry stores (value, current_min) so the min travels with it. Example: Min Stack.
• Two-stack with auxiliary min: push to the min stack only when the new value ties or beats the current min. Example: Min Stack.
• Max stack with O(log n) popMax: pair the stack with a sorted structure or doubly linked list for the extra operation. Example: Max Stack.
• Min queue via two min-stacks: emulate a queue with two stacks, each tracking its own running min. Example: Sliding Window Maximum.