How do you design a min stack with O(1) getMin? | Interview Question

Q: How do you design a min stack with O(1) getMin?

**Target Audience:** Beginners preparing for coding interviews; you should know what a stack is. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the **Verified** section quotes the real output. ## 1. Why This Even Matters — A Story First Picture a pile of exam papers on a teacher's desk. Papers are added and removed only from the top. The head teacher keeps walking in and asking one question: "What is the lowest mark in the pile right now?" Searching the whole pile each time is slow. So the teacher writes a small note in the corner of each paper as it goes on the pile: *"lowest mark from here down: 42"*. Now the answer is always written on the top paper. When a paper is taken off, the paper below it already carries the correct note for the smaller pile. That is

The problem

Question presented to candidate: "Design a stack class in Python that supports push, pop, top and get_min, where every one of those operations runs in O(1) time. Talk me through how you keep the minimum correct after a pop."

What a strong answer should cover:

Why a single current-minimum variable fails after popping the minimum.
Storing (value, minimum so far) on each entry, or an auxiliary mins stack that is pushed on <=.
All four operations O(1); O(n) extra space, and when the two-stack version saves memory.
The duplicate-minimum case, and why < instead of <= breaks it.
Python specifics: a list of tuples as the stack; min(self.stack) would be O(n); stack[-1] on an empty list raises IndexError; Python ints never overflow, so the encoded-difference trick is safe here.

Clarifying questions expected:

"What should top or get_min do on an empty stack?"
"Can values repeat?"

Code / implementation expected: Yes — a Python class backed by a list of (value, min) tuples.

dsa
stack
design

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews; you should know what a stack is. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every code block in this Python version was run, and the Verified section quotes the real output.

1. Why This Even Matters — A Story First

Picture a pile of exam papers on a teacher's desk. Papers are added and removed only from the top. The head teacher keeps walking in and asking one question: "What is the lowest mark in the pile right now?" Searching the whole pile each time is slow. So the teacher writes a small note in the corner of each paper as it goes on the pile: "lowest mark from here down: 42". Now the answer is always written on the top paper. When a pap

The solution is hidden so you can try first

4 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonMin stack of (value, min) pairs, including duplicate minimums

Practice

PythonTwo-stack version: the < versus <= bug, and memory use

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.