Min / Max Stack

Before we start

The Min Stack is a classic design question — it appears in nearly every FAANG interview list. The challenge is that a standard stack gives you O(n) getMin (scan all elements). This note shows you why that's bad and exactly how to get O(1) without sacrificing any of the other stack operations. By the end you will be able to:

• Explain the auxiliary stack idea and why it stays synchronized with the main stack.
• Write the full MinStack class from memory with all four operations.
• Adapt it to a Max Stack and handle a tricky "pop restores previous min" edge case correctly.

Picture this first (no code yet)

The actual problem

Min Stack (LC #155):

Design a stack that supports:

• push(val) — push element onto the stack.
• pop() — remove top element.
• top() — get the top element.
• getMin() — retrieve the minimum element in the stack.

All operations must run in O(1) time.

First, the slow way (so you feel the pain)

Keep a single list. getMin() scans all n elements: min(self.stack). For 1,000,000 elements and 1,000,000 getMin() calls, that is 10¹² operations — over an hour. Trading a tiny bit of extra space (O(n) for a second stack) brings this to O(1) per operation.

The turning point

The one idea to remember

The code

class MinStack:
    def __init__(self):
        self.stack     = []   # main stack: holds actual values
        self.min_stack = []   # auxiliary: top is current minimum

    def push(self, val: int) -> None:
        self.stack.append(val)
        # new minimum is: val if min_stack is empty, else min of val and current min
        curr_min = val if not self.min_stack else min(val, self.min_stack[-1])
        self.min_stack.append(curr_min)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()   # discard corresponding minimum snapshot

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

    def getMin(self) -> int:
        return self.min_stack[-1]   # always the current min — O(1)

Line-by-line narration:

1. self.stack — the real stack.
2. self.min_stack — a parallel stack; min_stack[i] is the minimum of all elements in stack[0..i].
3. push: append val to main, compute new snapshot min (min of val and previous snapshot), append to min_stack. Both stacks grow in lockstep.
4. pop: discard from both. min_stack automatically reverts to the previous snapshot — the old minimum.
5. top: standard stack top.
6. getMin: just min_stack[-1] — O(1).

Watch it happen, frame by frame

Operations: push(5), push(3), push(7), push(2), pop(), getMin()

push(5):  stack=[5],       min_stack=[5]
push(3):  stack=[5,3],     min_stack=[5,3]    (min(3,5)=3)
push(7):  stack=[5,3,7],   min_stack=[5,3,3]  (min(7,3)=3)
push(2):  stack=[5,3,7,2], min_stack=[5,3,3,2]

getMin() → min_stack[-1] = 2  ✅

pop():    stack=[5,3,7],   min_stack=[5,3,3]  (2 popped from both)

getMin() → min_stack[-1] = 3  ✅  (reverted to previous min)

The critical moment: popping 2 correctly reveals that the minimum is now 3 again — no scan needed.

Space optimization: store only when minimum changes

If memory is tight, only push to min_stack when the new value is ≤ the current minimum. Pop from min_stack only when the popped value equals the current minimum:

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()

Trade-off: uses less space when many pushes don't change the minimum, but requires the == comparison on pop. The full parallel approach is simpler and avoids this subtlety.

Max Stack variant

Identical structure, just track the running maximum:

class MaxStack:
    def __init__(self):
        self.stack     = []
        self.max_stack = []

    def push(self, val):
        self.stack.append(val)
        curr_max = val if not self.max_stack else max(val, self.max_stack[-1])
        self.max_stack.append(curr_max)

    def pop(self):
        self.stack.pop()
        self.max_stack.pop()

    def getMax(self):
        return self.max_stack[-1]

Both min and max simultaneously

If a problem needs O(1) getMin AND getMax, maintain two auxiliary stacks — min_stack and max_stack — both synchronized with the main stack:

def push(self, val):
    self.stack.append(val)
    self.min_stack.append(min(val, self.min_stack[-1]) if self.min_stack else val)
    self.max_stack.append(max(val, self.max_stack[-1]) if self.max_stack else val)

def pop(self):
    self.stack.pop()
    self.min_stack.pop()
    self.max_stack.pop()

Where this pattern appears

Trigger words:

• "design a stack that supports getMin/getMax in O(1)"
• "sliding window minimum/maximum" — a related but different technique using a deque (Chapter 6.02)
• any problem where you need to query a property of the entire stack's current contents in O(1)

Problems:

1. Min Stack (LC #155): direct application.
2. Max Stack (LC #716): also requires popMax() — needs a doubly linked list + heap combination for full O(log n) complexity.
3. Maximum Frequency Stack (LC #895): design a stack where pop returns the most frequent element — uses a frequency map and a stack per frequency level.

Common traps

class MinStack:
    def __init__(self):
        self.s, self.m = [], []

    def push(self, val):
        self.s.append(val)
        self.m.append(min(val, self.m[-1]) if self.m else val)

    def pop(self):
        self.s.pop(); self.m.pop()

    def top(self):      return self.s[-1]
    def getMin(self):   return self.m[-1]

Check yourself

Practice problems

Next up: Largest Rectangle in Histogram — the most celebrated monotonic stack application, finding the largest rectangle in O(n) by using previous-smaller and next-smaller boundaries simultaneously.