How to Explain Min Stack in a Coding Interview (Step-by-Step)

Min Stack is a data structure design problem that looks deceptively simple — until you realise that a standard stack loses minimum information the moment you pop. The key is maintaining an auxiliary min-stack that tracks the running minimum at every level, ensuring getMin() is always O(1) no matter what gets pushed or popped.

In this post, you’ll learn exactly how to walk an interviewer through LeetCode 155: the problem with naïve approaches, the dual-stack design, the synchronisation rule between stacks, a full operation trace, and every edge case worth naming.

Problem Statement

Example

Constraints

• -231 <= val <= 231 - 1
• pop(), top(), getMin() will always be called on a non-empty stack
• At most 3 * 104 operations

What Is the Problem?

“I need to design a stack where every operation — including retrieving the current minimum — runs in O(1). A standard stack already gives O(1) for push, pop, and top. The hard part is getMin(). If I scan the whole stack for the minimum each time, that’s O(n). I need to track the minimum incrementally as elements are pushed and popped.”

Identifying that getMin() is the only challenging operation — and that the other three are trivially O(1) on a normal stack — tells the interviewer you’ve precisely located the difficulty before reaching for a solution.

Step 1: Compare Approaches Before Jumping to Code

“The single-variable approach breaks the moment you pop the current minimum — you’d need to scan the remaining stack to find the new minimum, which is O(n). The auxiliary stack solves this by remembering, at every depth, what the minimum was at that point in time. When you pop the main stack, you also pop the min-stack — and the new top of the min-stack is the correct minimum for whatever is left.”

The Key Insight — Track the Minimum at Every Level

The Dual-Stack Design

Step 2: Explain the Algorithm in Plain English

Operation Trace — push(-2), push(0), push(-3), getMin, pop, top, getMin

Tracing every operation. Blue = main stack, Purple = min-stack. The top of the min-stack is always the current minimum.

Step 3: Talk Through the Code

class MinStack:

    def __init__(self):
        self.stack     = []   # Main stack — stores all values
        self.min_stack = []   # Auxiliary stack — top is always the current minimum

    def push(self, val: int) -> None:
        self.stack.append(val)
        # Current minimum is the smaller of val and whatever minimum was before
        if self.min_stack:
            self.min_stack.append(min(val, self.min_stack[-1]))
        else:
            self.min_stack.append(val)   # First push — val is trivially the minimum

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()   # Always pop both — stacks are always the same size

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

    def getMin(self) -> int:
        return self.min_stack[-1]   # O(1) — answer is always at the top

Three things to narrate explicitly: (1) the two stacks are always kept the same size — every push adds to both, every pop removes from both; (2) the min-stack entry on push is min(val, min_stack[-1]) — this is what makes the minimum “sticky” even when the incoming value isn’t a new minimum; (3) getMin() is a single array lookup — no scan, no sort, no computation.

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

“Every operation is O(1). The cost is space — we use O(n) for the auxiliary min-stack on top of the O(n) main stack. The follow-up question is often ‘can you do it with less space?’ You can optimise slightly by only pushing to the min-stack when the new value is ≤ the current minimum, and only popping the min-stack when the popped value equals the current minimum — but this complicates the code. The simpler always-in-sync approach is preferred unless the interviewer pushes for the optimisation.”

Interview Checklist for Min Stack

• Restate — “all four operations must be O(1), including getMin”
• Identify getMin as the only non-trivial operation — others are standard stack
• Explain why scanning fails (O(n)) and why a single variable fails (can’t recover after pop)
• Name the auxiliary min-stack pattern and state its invariant: top always holds the current minimum
• Describe push: append to both stacks, min-stack gets min(val, min_stack[-1])
• Describe pop: pop both stacks simultaneously — stacks are always the same size
• Describe getMin: single O(1) lookup at min_stack[-1]
• Explain why duplicate values must be pushed to the min-stack — keeps stacks in sync
• Mention the space-optimised variant (only push to min-stack on new minimums) as a follow-up
• State O(1) per operation and O(n) total space

Related Problems to Practice

If you can explain Min Stack cleanly, try these next: