LeetCode #155: Min Stack — Design a Stack with O(1) Minimum Retrieval

LeetCode Problem: #155 — Min Stack
Difficulty: Medium
Topics: Stack, Design, Data Structures
Pattern: Auxiliary Stack / Constant-Time State Tracking
Series: LeetCode Interview Preparation — From Beginner to Expert

In the previous article, we learned how a Stack can solve problems involving nested structures.

Now we're going to take the same data structure and make it more powerful.

Imagine you're asked to design a stack that supports:

push()
pop()
top()
getMin()

But there's one important requirement:

getMin() must return the minimum element in O(1) time.

At first, this sounds easy.

But there's a catch.

If we simply search the stack every time getMin() is called, we get:

O(n)

per query.

The goal is:

push()   → O(1)
pop()    → O(1)
top()    → O(1)
getMin() → O(1)

This problem teaches an extremely valuable interview technique:

Maintain additional information while processing data so that future queries become cheap.

The Problem

Design a stack that supports the following operations:

push(val)
pop()
top()
getMin()

All operations must run in:

O(1)

time.

What Does Each Operation Mean?

push(val)

Add val to the stack.

pop()

Remove the element at the top.

top()

Return the element currently at the top.

getMin()

Return the smallest element currently present in the stack.

Example

Let's perform:

push(-2)
push(0)
push(-3)

The stack is:

-3  ← top
 0
-2

Minimum:

-3

So:

getMin() → -3

Now:

pop()

removes -3.

Stack:

 0  ← top
-2

Now:

getMin() → -2

The Obvious Solution

Let's start with the simplest idea.

Use one normal stack:

stack = []

For:

push(5)
push(2)
push(8)
push(1)

we have:

[5, 2, 8, 1]

To find the minimum, we could do:

min(stack)

But:

min(stack)

requires scanning the entire stack.

That's:

O(n)

So although:

push → O(1)
pop  → O(1)
top  → O(1)

we get:

getMin → O(n)

That doesn't satisfy the problem.

Can We Remember the Minimum?

Yes.

This is the key insight.

Suppose our stack is:

5
2
8
1

The minimum is:

1

But if we pop 1, the minimum becomes:

2

So we need to know not only the current minimum, but the minimum at every level of the stack.

That's where an auxiliary stack comes in.

The Two-Stack Approach

We'll maintain two stacks:

Normal Stack

Stores the actual values.

stack

Minimum Stack

Stores the minimum value at each level.

minStack

For example:

push(5)

Normal stack:

[5]

Minimum stack:

[5]

Then:

push(2)

Normal stack:

[5, 2]

Minimum stack:

[5, 2]

Because the minimum is now 2.

Then:

push(8)

Normal:

[5, 2, 8]

Minimum:

[5, 2, 2]

Notice something important.

We don't store 8 in the minimum stack.

Instead, we store:

current minimum

at that point.

Then:

push(1)

Normal:

[5, 2, 8, 1]

Minimum:

[5, 2, 2, 1]

Now getMin() is incredibly easy.

Simply return:

minStack[-1]

That's:

O(1)

Why Does This Work?

The minimum stack remembers the answer to:

"What is the minimum of everything in the stack up to this point?"

For:

[5, 2, 8, 1]

we maintain:

[5, 2, 2, 1]

Each position corresponds to the same position in the main stack.

Therefore:

minStack[-1]

always represents the minimum of the entire current stack.

Python Implementation

class MinStack:

    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val):
        self.stack.append(val)

        if not self.minStack:
            self.minStack.append(val)
        else:
            self.minStack.append(
                min(val, self.minStack[-1])
            )

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

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

    def getMin(self):
        return self.minStack[-1]

This is the cleanest approach to understand first.

Understanding push()

The important line is:

self.minStack.append(
    min(val, self.minStack[-1])
)

Suppose:

current minimum = 3
new value = 5

Then:

min(5, 3) = 3

So we store:

3

But if:

current minimum = 3
new value = 1

then:

min(1, 3) = 1

So the new minimum becomes:

1

Understanding pop()

When we remove the top element:

self.stack.pop()

we must also remove the corresponding minimum:

self.minStack.pop()

This keeps both stacks synchronized.

Understanding top()

Simple:

return self.stack[-1]

The top of a Python list is:

stack[-1]

Understanding getMin()

This is the entire reason we created minStack.

return self.minStack[-1]

No scanning.

No sorting.

No iteration.

Just one lookup.

Therefore:

O(1)

Full Dry Run

Let's execute:

push(5)
push(2)
push(8)
push(1)
getMin()
pop()
getMin()
top()

Operation 1

push(5)

Stack:

[5]

Min Stack:

[5]

Operation 2

push(2)

Stack:

[5, 2]

Min Stack:

[5, 2]

Operation 3

push(8)

Stack:

[5, 2, 8]

Min Stack:

[5, 2, 2]

Operation 4

push(1)

Stack:

[5, 2, 8, 1]

Min Stack:

[5, 2, 2, 1]

Operation 5

getMin()

Return:

1

Operation 6

pop()

Both stacks become:

Stack:
[5, 2, 8]

Min Stack:
[5, 2, 2]

Operation 7

getMin()

Return:

2

Operation 8

top()

Return:

8

Everything works in constant time.

Why Not Store Only New Minimums?

You might propose this:

minStack = [5, 2, 1]

instead of:

minStack = [5, 2, 2, 1]

That can also work.

The idea would be to store a value only when it becomes a new minimum.

For example:

push(5) → minStack [5]
push(2) → minStack [5, 2]
push(8) → minStack [5, 2]
push(1) → minStack [5, 2, 1]

But then pop() needs to know whether the removed value equals the current minimum.

That approach is valid, but the synchronized two-stack approach is often easier to reason about and implement correctly.

Space-Optimized Version

There's another elegant approach.

Instead of maintaining two separate stacks, we can store pairs:

(value, minimum_so_far)

For example:

(5, 5)
(2, 2)
(8, 2)
(1, 1)

Then the minimum is always the second value of the top pair.

Python Version Using One Stack

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val):
        if not self.stack:
            current_min = val
        else:
            current_min = min(
                val,
                self.stack[-1][1]
            )

        self.stack.append((val, current_min))

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

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

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

This is conceptually the same technique.

We're simply storing:

value
+
minimum so far

together.

The Bigger Pattern: Maintain State

This problem teaches a pattern that appears far beyond stacks.

Suppose you're repeatedly asked:

"What is the minimum so far?"

Instead of recalculating it every time, maintain:

minimum_so_far

This is a general algorithmic technique:

Precompute or maintain useful state so future queries are cheap.

We've already seen a similar idea in our stock problem:

minimum price seen so far

Here we're doing something similar:

minimum value at each stack level

Connection to Prefix Techniques

This idea also connects to prefix data structures.

For example:

nums = [5, 2, 8, 1]

Prefix minimums are:

[5, 2, 2, 1]

That's exactly what our minStack stores.

So Min Stack can be thought of as:

Prefix minimum tracking + stack operations.

Recognizing these connections makes new problems easier.

Handling Duplicate Minimums

Consider:

push(2)
push(2)
push(5)

Our stacks become:

Stack:
[2, 2, 5]

Min Stack:
[2, 2, 2]

Now:

pop()

Min Stack:

[2, 2]

Minimum is still:

2

Another pop:

[2]

Minimum remains:

2

This is why storing the minimum at every level is so convenient.

Handling Negative Numbers

Nothing special is required.

For:

push(-2)
push(-10)
push(-3)

Min Stack:

[-2, -10, -10]

Therefore:

getMin() → -10

Common Mistake #1: Calculating min() During getMin()

This:

def getMin(self):
    return min(self.stack)

is easy to write.

But it takes:

O(n)

and violates the requirement.

The whole point is to maintain the minimum proactively.

Common Mistake #2: Forgetting to Update minStack During pop()

If you do:

self.stack.pop()

but forget:

self.minStack.pop()

the two structures become inconsistent.

Every stack operation must maintain the relationship between the two stacks.

Common Mistake #3: Storing Only the Current Minimum

Suppose:

[5, 2, 8, 1]

and you only store:

minimum = 1

After popping 1, you would need to rediscover that the previous minimum was 2.

That's why we preserve historical minimum information.

Common Mistake #4: Confusing top() and getMin()

They are different questions.

top()

asks:

What was added most recently?

While:

getMin()

asks:

What is the smallest value?

The two-stack design maintains both independently.

Interview Follow-Up: Get Maximum Too

What if the stack needs:

getMin()
getMax()

in O(1)?

You could maintain:

stack
minStack
maxStack

Now all three operations remain O(1).

Interview Follow-Up: Get Average

What if the interviewer asks for:

getAverage()

You could maintain a running sum.

Then:

average = sum / count

Again, the same principle:

Maintain state while updates occur.

Interview Follow-Up: Get Second Minimum

Now things become more interesting.

A single minimum isn't enough.

You need additional information about the second-smallest value and how it changes during pop().

This is where interviewers start testing whether you understand the underlying state-maintenance technique rather than just memorizing the standard Min Stack solution.

Interview Follow-Up: Memory Constraints

Suppose memory is extremely limited.

Can you still support:

getMin()

in O(1)?

This becomes a much more advanced design question.

There are mathematical encoding techniques that can reduce auxiliary storage, but they make the implementation more complex and can introduce integer-overflow considerations in some languages.

For most interviews, the auxiliary-stack solution is the clean trade-off.

Why O(1) getMin() Is Possible

This is worth understanding deeply.

A normal stack gives us:

top()

in O(1).

But it doesn't naturally give:

minimum()

in O(1).

So we augment the data structure.

Instead of storing only:

value

we store:

value
minimum_so_far

Now every stack entry carries enough information to answer the minimum query immediately.

This is called augmenting a data structure.

That concept is extremely useful in advanced software engineering interviews.

Pattern Recognition

When an interviewer says:

"Support an operation in O(1), but the normal data structure would require O(n)."

Ask:

"Can I maintain extra information during updates?"

Examples:

Stack
+
Minimum

Array
+
Prefix information

Queue
+
Maximum information

Data structure
+
Cached state

The general pattern is:

Expensive query
       ↓
Maintain state during updates
       ↓
Cheap query

Real-World Analogy

Imagine you're running a competition.

Instead of checking every participant whenever someone asks:

"What's the lowest score so far?"

you maintain:

lowest_score

Whenever a new score arrives:

lowest_score = min(
    lowest_score,
    new_score
)

Now answering the query takes:

O(1)

Min Stack is the same idea, except we also need to correctly restore the previous state when elements are removed.

Complexity Table

Overall auxiliary space:

O(n)

because we store minimum information for the elements in the stack.

Interview Cheat Sheet

Problem:
Design a stack with getMin().

Required:
push()  → O(1)
pop()   → O(1)
top()   → O(1)
getMin() → O(1)

Idea:
Use an auxiliary minimum stack.

Main Stack:
stores values.

Min Stack:
stores minimum so far.

push(x):
    stack.push(x)
    minStack.push(
        min(x, minStack.top())
    )

pop():
    stack.pop()
    minStack.pop()

top():
    return stack.top()

getMin():
    return minStack.top()

Time:
O(1) per operation

Space:
O(n)

Practice Challenges

Try these before moving to the next problem.

Challenge 1

Implement Min Stack using two stacks without using Python's built-in min().

Challenge 2

Implement:

getMax()

in O(1).

Challenge 3

Implement a stack supporting both:

getMin()
getMax()

in O(1).

Challenge 4

Design a queue supporting:

enqueue()
dequeue()
getMin()

in O(1).

Challenge 5

Modify Min Stack so it can also return the frequency of the minimum value.

Challenge 6

Try solving Min Stack using a single stack of tuples.

The Pattern Library So Far

Our interview preparation journey is now building a stronger foundation.

The important progression is:

Stack
 ↓
Valid Parentheses
 ↓
Understand LIFO
 ↓
Min Stack
 ↓
Augment the Stack
 ↓
Maintain Extra State

We're moving from simply using data structures to designing data structures.

That's an important jump in interview preparation.

Final Takeaway

LeetCode #155 teaches much more than how to implement a minimum stack.

The real lesson is:

Don't repeatedly calculate information that you can maintain incrementally.

A normal stack knows:

What is on top?

An augmented stack can also know:

What is the minimum?

without scanning the entire structure.

The transformation is:

Normal Stack
     ↓
Add auxiliary state
     ↓
Track minimum after every update
     ↓
getMin() becomes O(1)

This is a pattern you'll encounter repeatedly in algorithm and system design interviews.

When you see a problem that says:

"Support operation X in constant time."

don't immediately assume you need a magical algorithm.

First ask:

"What information can I maintain now so I don't have to calculate it later?"

That question can lead you to the solution.