Cracking The Coding Interview Together – Problem 3.2: Stack Min

Alright.

Let’s continue our journey in Cracking The Coding Interview — Together.

And as always, we are not here to just “solve” the problem.

We are here to think like engineers.
To communicate like interview candidates.
To reason like problem solvers.

Today’s problem is deceptively simple.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element?

All three operations — push, pop, and min — should operate in O(1) time.

Analyse the problem statement together

We all know what a stack is.

• LIFO (Last In First Out)
• push → add element to top
• pop → remove top element
• peek → see top element

Now the twist:

We need an additional function:

min()

which returns the smallest element currently in the stack.

And not in O(n).
Not by scanning the stack.
Not by sorting.

It must be O(1).

That constraint is the real problem here.

Let’s pause.

If I gave you a normal stack and asked:

“What’s the minimum element?”

You’d have to scan all elements. That’s O(n).

But here, the interviewer is saying:

“I want you to be smarter.”

And that’s where design thinking comes in.

Questions for the interviewer

Before we go forward, what questions come to your mind?

Think. Really think.

Here are mine:

1. Can duplicate values exist in the stack?
2. Can negative numbers exist?
3. What should min() return if the stack is empty?
4. Are we allowed to use additional data structures internally?
5. Is this supposed to be a wrapper around an existing stack, or a custom implementation?

Most likely answers:

• Yes, duplicates are allowed.
• Yes, negative numbers are allowed.
• Throw an exception or handle empty case appropriately.
• Yes, we can use extra space internally.
• We should implement our own stack.

Good.

Now we can move ahead with clarity.

Think about the Solution

Close this tab for two minutes.

Ask yourself:

How can I always know the minimum element without scanning?

What information must I preserve while pushing and popping?

Don’t read further until you have at least one idea.

…

Okay. Let’s discuss.

Think Out Loud: How Would You Approach This?

Let’s start naïve.

Brute Force Idea

Every time someone calls min(), we iterate through the stack.

Time complexity:

• push() → O(1)
• pop() → O(1)
• min() → O(n)

Rejected.

The problem clearly demands O(1) for everything.

Key Insight

The minimum value changes only when:

• We push a new smaller value.
• We pop the current minimum.

That’s it.

So maybe…

Instead of recalculating the minimum every time,
we track it as we go.

Now we are thinking in the right direction.

First Better Approach — Two Stacks

Imagine this:

We maintain:

1. Main stack → normal stack.
2. Min stack → keeps track of minimums.

How would this work?

Push Logic

When pushing a value:

• Push it onto main stack.
• If min stack is empty OR value ≤ current minimum → push onto min stack.

Pop Logic

When popping:

• Pop from main stack.
• If popped value equals top of min stack → pop from min stack too.

Min Logic

Just return top of min stack.

Now let’s simulate.

Example Walkthrough

Push 5
Main: [5]
Min: [5]

Push 3
Main: [5, 3]
Min: [5, 3]

Push 7
Main: [5, 3, 7]
Min: [5, 3]

Push 2
Main: [5, 3, 7, 2]
Min: [5, 3, 2]

Now min() → 2

Pop
Main: [5, 3, 7]
Min: [5, 3]

min() → 3

Beautiful.

Everything is O(1).

Can We Do Even Better?

Yes.

There’s a more elegant design.

Instead of two stacks,
we can store extra information in each node.

This is what separates a good answer from a great answer.

Optimized Unified Design — Storing Min with Each Node

Instead of maintaining two stacks separately, we create a custom node like this:

Each node stores:

• value
• minSoFar

So every node knows:

“What was the minimum at the time I was pushed?”

Now the logic becomes even cleaner.

Push Logic

When pushing new value:

newMin = min(value, currentMin)

Create node(value, newMin)

Push it.

Pop Logic

Just pop normally.

Because the previous node already knows what its minimum was.

Min Logic

newMin = min(value, currentMin)

That’s it.

No comparison needed during pop.

Very clean.

Very elegant.

Write code and explain

Now let’s translate this idea into code.

Java code

public class MinStack {

    private static class Node {
        int value;
        int min;
        Node next;

        Node(int value, int min) {
            this.value = value;
            this.min = min;
        }
    }

    private Node top;

    public void push(int value) {
        if (top == null) {
            top = new Node(value, value);
        } else {
            int newMin = Math.min(value, top.min);
            Node newNode = new Node(value, newMin);
            newNode.next = top;
            top = newNode;
        }
    }

    public int pop() {
        if (top == null) {
            throw new RuntimeException("Stack is empty");
        }

        int value = top.value;
        top = top.next;
        return value;
    }

    public int min() {
        if (top == null) {
            throw new RuntimeException("Stack is empty");
        }

        return top.min;
    }

    public int peek() {
        if (top == null) {
            throw new RuntimeException("Stack is empty");
        }

        return top.value;
    }
}

Explain the Code in Plain English

You don’t just write code.

You explain your design.

You say:

“Each node stores the minimum value at the time it was inserted. This allows us to retrieve the minimum in constant time without needing an additional stack or traversal. When popping, the previous node already contains the correct minimum for the remaining stack.”

This shows clarity.

This shows intention.

This shows engineering maturity.

Time & Space Complexity

Time Complexity

• push → O(1)
• pop → O(1)
• min → O(1)
• peek → O(1)

Space Complexity

O(n)

Each node stores one extra integer.

That’s constant extra space per node.

Totally acceptable tradeoff.

Final Thoughts

This problem is small.

But it carries a big lesson.

Most interview problems are not about code.

They are about:

• Can you reason about state?
• Can you design clean abstractions?
• Can you explain tradeoffs clearly?

If you understood this deeply,
you are no longer “just solving problems”.

You are designing systems.

And that is what interviews are actually testing.