Min Stack

Table of Contents +

A normal stack can push, pop, and show you the top item fast. But what if the interviewer asks for one more thing? They want the smallest element in the stack at any moment. And they want it instantly. This question looks simple. But it is really checking if you can keep extra information in sync as the stack changes. Let us see what they are testing.

🧠 The Problem

You have to design a stack that supports the usual operations, plus one special operation called getMin. Here is what each one does.

push(x) — add x on top of the stack.
pop() — remove the top element.
top() — look at the top element.
getMin() — return the smallest element currently in the stack.

The catch is that every single one of these must run in O(1) time. O(1) means constant time. So the work does not grow even when the stack has a million elements.

Operations:
push(5), push(3), push(7), getMin()  ->  3
pop(), getMin()                       ->  3
pop(), getMin()                       ->  5

🐌 The Simple Idea (and why it breaks)

Your first thought might be this. I will keep one variable called min. Every time I push a number, I check if it is smaller than min. If it is, I update min. So getMin just returns that variable. Fast, right?

It works fine until you pop. Say you pushed 5, then 3. Now min is 3. Then you pop the 3. The smallest left is 5. But your min variable still says 3. You have no way to know the previous minimum. You threw that information away.

You could scan the whole stack again to find the new minimum. But scanning is O(n). That breaks the O(1) promise. So a single min variable is not enough.

✅ The Optimal Idea: a second stack

The trick is to remember the minimum at every level, not just the latest one. We keep a second stack. We call it the min stack. It runs side by side with the main stack.

Think of it like a stack of plates where each plate also has a sticky note. The note says “the smallest plate from here down”. So when you lift a plate off, the note on the next plate already tells you the new minimum. You never lose the old answer. Each level remembers its own minimum.

Here is the rule. When you push a number, you also push the smaller of (the new number, the current min) onto the min stack. When you pop, you pop from both stacks together. So the top of the min stack is always the minimum of everything still in the main stack.

Note

Both stacks always have the same height. So getMin is just “look at the top of the min stack”. That is one read. Pure O(1).

📝 Steps to build it

Here is the plan, step by step. Each step keeps the two stacks lined up so the minimum is always one read away.

Create two empty stacks: mainStack for the values and minStack for the running minimum.
On push(x), push x onto mainStack. Then look at the top of minStack. Push the smaller of x and that top onto minStack. If minStack is empty, just push x.
On pop(), remove the top from both mainStack and minStack.
On top(), return the top of mainStack.
On getMin(), return the top of minStack.

💻 The Code

Below is a full Min Stack with all four operations, plus a small demo that prints the result of each step.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

class MinStack:
    def __init__(self):
        self.main_stack = []
        self.min_stack = []  # last item is the current minimum

    def push(self, x):
        self.main_stack.append(x)
        # store the smaller of x and the current minimum
        if not self.min_stack or x < self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self):
        self.main_stack.pop()
        self.min_stack.pop()  # pop from both together

    def top(self):
        return self.main_stack[-1]

    def get_min(self):
        return self.min_stack[-1]


s = MinStack()
s.push(5)
s.push(3)
s.push(7)
print("getMin:", s.get_min())  # 3
s.pop()
print("getMin:", s.get_min())  # 3
s.pop()
print("top:", s.top())         # 5
print("getMin:", s.get_min())  # 5

The output of the above code will be:

getMin: 3
getMin: 3
top: 5
getMin: 5

⏱️ Time and Space Complexity

Here is how the two ideas compare. The single-variable idea looks lighter on memory. But it cannot keep getMin fast after a pop. The two-stack idea pays a little extra memory and keeps every operation at O(1).

Approach	getMin Time	push / pop / top Time	Space
Single min variable (rescan on pop)	O(n)	O(1)	O(n)
Two stacks (min stack)	O(1)	O(1)	O(n)

Tip

If the interviewer asks you to save memory, mention this. Instead of pushing a value on the min stack every single time, push only when the new number is smaller than or equal to the current min. On pop, you remove from the min stack only when the popped value equals its top. Say “equal to” out loud. Duplicates of the minimum will trip you up if you forget them.

🧩 Key Takeaways

✅ A single min variable fails because a pop can remove the current minimum and you lose the previous one.
✅ A second stack remembers the minimum at every level, so you never lose old answers.
✅ Push the smaller of (new value, current min) onto the min stack on every push.
✅ Pop from both stacks together so their tops always line up.
✅ Every operation, including getMin, runs in O(1) time.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Introduction to Stack
Implement a Queue using Stacks

Previous Next Greater Element Next Implement a Queue using Stacks

Share & Connect

Share on LinkedIn