Min Stack

leetcode.com

Problem Statement

Design a stack that supports the following operations in O(1) time:

push(x)

pop()

top()

getMin()

getMin() should always return the minimum element currently present in the stack.

---

Brute Force Intuition

In an interview, you can explain it like this:

We can use a normal stack. Whenever getMin() is called, simply traverse the entire stack and find the minimum element.

This works, but every getMin() requires scanning all elements.

Complexity

Operation	Complexity
push	O(1)
pop	O(1)
top	O(1)
getMin	O(N)

Brute Force Code

class MinStack {

    Stack<Integer> st;

    public MinStack() {
        st = new Stack<>();
    }

    public void push(int val) {
        st.push(val);
    }

    public void pop() {
        st.pop();
    }

    public int top() {
        return st.peek();
    }

    public int getMin() {

        int min = Integer.MAX_VALUE;

        for (int num : st) {
            min = Math.min(min, num);
        }

        return min;
    }
}

---

Moving Towards the Optimal Approach

The problem is:

Finding Minimum

Instead of searching every time,

why not store the minimum while inserting elements?

Maintain another stack that stores:

Current Minimum

at every stage.

---

Pattern Recognition

Whenever you see:

• Stack
• Current Minimum / Maximum
• O(1) Query

Think:

Two Stacks

---

Key Observation

Main Stack:

5

2

8

1

Min Stack:

5

2

2

1

Top of Min Stack always stores:

Minimum Element

---

Optimal Approach

Push

Push into main stack.

If:

Current element <= current minimum

also push into min stack.

---

Pop

If popped element equals:

Minimum

remove from min stack too.

---

getMin()

Simply return:

Top of Min Stack

---

Optimal Java Solution

class MinStack {

    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {

        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {

        stack.push(val);

        if (minStack.isEmpty()
            || val <= minStack.peek()) {

            minStack.push(val);
        }
    }

    public void pop() {

        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }

        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

---

Dry Run

Operations

push(5)

Main Stack:

5

Min Stack:

5

---

push(2)

Main:

2
5

Min:

2
5

---

push(8)

Main:

8
2
5

Min:

2
5

Minimum:

2

---

push(1)

Main:

1
8
2
5

Min:

1
2
5

Minimum:

1

---

pop()

Remove:

1

Main:

8
2
5

Min:

2
5

Minimum:

2

---

Why Two Stacks Work?

Every minimum value is stored separately.

Whenever the minimum element is removed:

Remove it from Min Stack too.

Thus:

Top of Min Stack

=

Current Minimum

without scanning the stack.

---

Complexity Analysis

Operation	Complexity
Push	O(1)
Pop	O(1)
Top	O(1)
Get Min	O(1)

---

Follow-Up (Optimal Space)

Instead of maintaining two stacks,

we can use:

One Stack

+

One Variable (min)

using an encoding technique.

This reduces auxiliary space while keeping all operations O(1).

---

Interview One-Liner

Maintain a second stack that stores the minimum element seen so far. The top of the second stack always represents the current minimum.

---

Pattern Learned

Stack

+

Need Current Minimum

↓

Extra Stack

Similar Problems

• Min Stack
• Max Stack
• Stock Span
• Daily Temperatures
• Largest Rectangle in Histogram

---

Memory Trick

Think:

Push

↓

Is New Minimum?

↓

Yes

↓

Push into Min Stack

Pop

↓

Removing Minimum?

↓

Pop from Min Stack

Mental Model

Main Stack

Stores All Values

↓

Min Stack

Stores Running Minimum

Whenever you hear:

"Design a stack supporting getMin() in O(1)"

your brain should immediately think:

Two Stacks (Main Stack + Min Stack)