Loading…

mediumStack QueueLC #155Frequently asked

Min Stack

Q: How do you solve Min Stack using the Single Min Variable / Scan on getMin (Baseline) approach?

When to use it: Mention to expose why the naive idea breaks under pop, motivating the auxiliary stack. Use a normal stack and either (a) keep one `min` field, or (b) scan the stack on each `getMin`. **Why it fails.** Option (a) breaks on `pop`: suppose you push 5 then 1 — `min` is 1. Pop the 1 and the true minimum is 5 again, but a single variable has no memory of the *previous* minimum, so it stays 1 (wrong). Option (b) is correct but `getMin` becomes `O(n)`, violating the constant-time requirement. Both shortcomings point to the same fix: we must remember the minimum *at every level*, not just the latest, so popping can roll it back. Time complexity: O(1) push/pop/top, O(n) getMin. Space complexity: O(n).

LCPractice

Stack & Queue · 2 of 17 · 9 min

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

In plain English

An ordinary stack gives O(1) push/pop/top but O(n) min. The challenge is making min O(1) too, even as elements are popped and the minimum changes. We attach, to each element, the minimum of the stack up to and including that element, so the current minimum is always visible at the top.

Examples

Example 1

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: [-3, 0, -2]
Note: getMin → -3 (min of {-2,0,-3}); pop removes -3; top → 0; getMin → -2 (min restored to before -3 was pushed).

Example 2

Input: push(2), push(2), getMin(), pop(), getMin()
Output: [2, 2]
Note: Duplicates: min stack holds [2,2]; popping one still leaves a 2 → getMin stays 2.

Example 3

Input: push(5), getMin(), top()
Output: [5, 5]
Note: Single element is both the top and the minimum.

Constraints

-2³¹ ≤ val ≤ 2³¹ − 1
pop, top and getMin are always called on non-empty stacks
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin

Clarifying questions4First question: Are pop/top/getMin ever called on an empty stack?Explore questions

Q1.Are pop/top/getMin ever called on an empty stack?
The constraints guarantee they aren't, so I don't need to throw — but I'll still handle the empty case correctly on the first push.
Q2.Can values be negative or duplicated?
Yes, the full int range and duplicates. Using <= vs < only matters for the space-optimized variant; the parallel-stack version handles duplicates trivially.
Q3.Does getMin remove the minimum or just report it?
Just reports it — it's a peek. The minimum only leaves when the element holding it is popped.
Q4.Is extra O(n) space acceptable for O(1) min?
Yes — the standard solution uses an auxiliary stack of the same size. If asked to reduce it, I'd store the min only when it changes, or encode deltas against the running min.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Keep an auxiliary 'min' stack alongside the main stack. Each time you push, also push the running minimum (min of the new value and the current min) onto the min stack; pop both together. getMin() is just the top of the min stack. Every operation — push, pop, top, getMin — is O(1). The trick is storing the minimum *as of each level*, so popping naturally restores the previous minimum.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can design a data structure that maintains an O(1) auxiliary query under pushes and pops — specifically, how popping rolls back the minimum without recomputation.

Where candidates slip

Storing a single 'min' variable that can't be restored after the minimum is popped, or scanning the stack for getMin() (O(n)).

How to stand out

Explain why a single min variable fails (it can't recover the previous min on pop), present the parallel min stack, and mention the space-saving 'store min only when it changes' or 'encode deltas' optimizations.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Single Min Variable / Scan on getMin (Baseline)	`O(1) push/pop/top, O(n) getMin`	`O(n)`	Mention to expose why the naive idea breaks under pop, motivating the auxiliary stack.	Read
2	Parallel Min Stack (Optimal)Optimal	`O(1) for all operations`	`O(n)`	The answer they want. Lead with 'store the running min at each level so pop restores it for free'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewNeed O(1) getMin on a stackMin changes as elements pop?YesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Single Min Variable / Scan on getMin (Baseline)

TimeO(1) push/pop/top, O(n) getMinSpaceO(n)

Mention to expose why the naive idea breaks under pop, motivating the auxiliary stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The easy part is push/pop/top on a normal stack. What goes wrong if you keep just one variable for the current minimum?

2Hint 2Explore hint

A lone min variable can't tell you what the minimum was BEFORE the current min was pushed — once you pop it, the previous min is lost.

3Hint 3Explore hint

You could rescan the whole stack for getMin instead, but that's O(n) and violates the requirement.

A · Core idea

Use a normal stack and either (a) keep one min field, or (b) scan the stack on each getMin.

Why it fails. Option (a) breaks on pop: suppose you push 5 then 1 — min is 1. Pop the 1 and the true minimum is 5 again, but a single variable has no memory of the previous minimum, so it stays 1 (wrong). Option (b) is correct but getMin becomes O(n), violating the constant-time requirement. Both shortcomings point to the same fix: we must remember the minimum at every level, not just the latest, so popping can roll it back.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

push(5), push(1), pop(), getMin()

push(5)

min = 5

Statemin=5

Final resultincorrect

C · Code with teaching comments

Reference implementation previewclass MinStackNaive { private Deque<Integer> stack = new ArrayDeque<>(); private int min = Integer.MAX_VALUE; public void push(int val) {Explore the full code

solution.javaJava

Single Min Variable / Scan on getMin (Baseline) — reference

2 teaching notes

1
class MinStackNaive {
2
    private Deque<Integer> stack = new ArrayDeque<>();
3
    private int min = Integer.MAX_VALUE;
4
 
5
    public void push(int val) {
6
        stack.push(val);
7
        // Captures the new min but discards the old one — irreversible.
8
        min = Math.min(min, val);   // can't be undone on pop
9
    }
10
 
11
    public void pop() {
12
        stack.pop();                // min is now possibly stale
13
    }
14
 
15
    public int top() { return stack.peek(); }
16
 
17
    // Returns a stale minimum once the true min has been popped.
18
    public int getMin() { return min; }   // WRONG after pops
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(1) push/pop/top, O(n) getMin timeO(n) spaceOpen the invariant and proofExplore the proof

The minimum is a stack-structured quantity itself — it changes and must be undone in LIFO order exactly like the data. That's the clue that the minimum belongs on its own stack.

ComplexityO(1) push/pop/top, O(n) getMin time, O(n) space — A single min variable can't be restored on pop; recomputing min by scanning is O(n) per call.

E · Edge cases and pitfalls2A single min variable cannot recover the previous minimum after a pop.Explore edge cases

Pitfalls

A single min variable cannot recover the previous minimum after a pop.
Rescanning the stack for getMin is correct but O(n), breaking the constraint.

03.2

Approach 2 of 2 · Optimal

Parallel Min Stack (Optimal)

TimeO(1) for all operationsSpaceO(n)

The answer they want. Lead with 'store the running min at each level so pop restores it for free'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The minimum changes in LIFO order just like the data does. What structure naturally undoes its most recent change first?

2Hint 2Explore hint

Keep a second stack the same height as the main one; at each level store the minimum of all elements at or below that level.

3Hint 3Explore hint

On push, push min(val, currentMin). On pop, pop both. getMin is the top of the min stack — O(1).

A · Core idea

Maintain two stacks: stack for the values and mins where each entry is the minimum of all elements at or below that position.

push(val). Push val onto stack. Compute the new running minimum as min(val, currentMin) — where currentMin is the top of mins, or val itself if mins is empty — and push that onto mins. Now mins's top always equals the minimum of the entire current stack.

pop(). Pop from both stacks. This is the crux: removing the top mins entry exposes the entry beneath it, which was computed as the minimum of everything still in the stack. So the previous minimum is restored automatically — no recomputation, no scan. This is precisely what the single-variable approach couldn't do.

top() and getMin(). Both are O(1) peeks: top() reads the top of stack, getMin() reads the top of mins.

Why each level stores its own min. Because the minimum is itself a LIFO quantity — it can change on push and must roll back on pop — it deserves its own stack. By caching min(val, currentMin) at push time, we pre-pay the comparison once and make every future getMin a free peek, and we make every pop a free restore.

Duplicates and negatives. Pushing min(val, currentMin) handles duplicates correctly: pushing 2 twice puts 2 on mins twice, so popping one leaves a 2 and getMin stays 2. Full-range and negative values work since we only compare, never assume sign.

Space optimizations (worth mentioning). Two common reductions: (1) push onto mins only when val <= currentMin, and on pop only remove from mins when the popped value equals mins's top — saves space when minimums repeat rarely; (2) store deltas against the running min in a single stack, recovering O(1) min with no second stack at the cost of trickier arithmetic.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Array state

push(-2)

stack & mins gain -2

min ↓

-2

[0]

Current pointerResolved stateNot processed

Final resultgetMin=-3, top=0, getMin=-2

C · Code with teaching comments

solution.javaJava

Parallel Min Stack (Optimal) — optimal

7 teaching notes

1
class MinStack {
2
    // Holds the actual values; ArrayDeque is the modern stack in Java.
3
    private final Deque<Integer> stack = new ArrayDeque<>();
4
    // Parallel stack: each entry is the min at or below its level.
5
    private final Deque<Integer> mins = new ArrayDeque<>();
6
 
7
    public MinStack() {
8
    }
9
 
10
    public void push(int val) {
11
        // Standard push of the value.
12
        stack.push(val);
13
        // First push → val is its own min; otherwise compare with the running min.
14
        int currentMin = mins.isEmpty() ? val : Math.min(val, mins.peek());
15
        // Keep mins the same height as stack so they pop together.
16
        mins.push(currentMin);
17
    }
18
 
19
    public void pop() {
20
        stack.pop();
21
        mins.pop();
22
    }
23
 
24
    public int top() {
25
        return stack.peek();
26
    }
27
 
28
    public int getMin() {
29
        // getMin is just the top of the min stack — O(1).
30
        return mins.peek();
31
    }
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(1) for all operations timeO(n) spaceOpen the invariant and proofExplore the proof

The reusable principle is 'carry the answer with the data so undo is free'. When a stack/queue must also answer an aggregate query in O(1), attach the aggregate to each element so the structure's own push/pop maintain it. The same idea builds a FIFO queue from two stacks and a max-stack by symmetry.

ComplexityO(1) for all operations time, O(n) space — push/pop/top/getMin each do a constant number of stack operations → O(1) each. The auxiliary stack mirrors the main one → O(n) extra space.

E · Edge cases and pitfalls8push(5) then getMin/top — First push: mins empty → currentMin = 5. getMin and top both return 5.Explore edge cases

Edge cases handled

push(5) then getMin/topFirst push: mins empty → currentMin = 5. getMin and top both return 5.
push(2), push(2), pop(), getMin()mins = [2, 2]; popping leaves [2] → getMin stays 2 (duplicates handled).
all negatives, e.g. push(-1), push(-5)min(-5, -1) = -5 pushed → getMin returns -5; signs irrelevant.
push then pop down to empty, then push againmins empties with stack; next push treats val as its own min — no stale state.

Pitfalls

Popping only one of the two stacks — they desync and getMin lies.
On the first push, calling mins.peek() on an empty stack — guard with isEmpty().
Storing only when val < currentMin without the matching conditional pop — under-pops the min stack.
Recomputing min by scanning instead of peeking — silently O(n).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass MinStack { private final Deque<Integer> stack = new ArrayDeque<>(); private final Deque<Integer> mins = new ArrayDeque<>(); public MinStack() {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Desynced stacks on pop

The two stacks must stay the same height. Popping only the value stack leaves a stale entry on the min stack, so getMin reports a minimum that's no longer present.

Explore the code comparison

Don't write this

public void pop() {
    stack.pop();   // forgot mins.pop()
}

Write this instead

public void pop() {
    stack.pop();
    mins.pop();
}

Peeking an empty min stack on first push

On the very first push there is no current minimum yet. Calling mins.peek()/mins[-1] throws or errors. Treat the first value as its own minimum.

Explore the code comparison

Don't write this

def push(self, val):
    self.stack.append(val)
    self.mins.append(min(val, self.mins[-1]))  # IndexError when empty

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Auxiliary min stack tracking the minimum per level

Code pattern to memorize

push(x):  stack.push(x); mins.push(min(x, mins.peek() if mins else x))
pop():    stack.pop(); mins.pop()
top():    return stack.peek()
getMin(): return mins.peek()

Rules to remember

1Push to both stacks on every push, and pop from both on every pop — keep them the same height.
2The value pushed onto the min stack is min(newValue, currentMin), so each level remembers the minimum of everything below it.
3getMin() and top() are pure peeks — O(1), no scanning.
4Popping the min stack automatically restores the previous minimum; that's why you never need to recompute it.
5Handle the empty case on the first push (no current min yet) — the first value is its own minimum.

Use this pattern when

A stack that must also report its min (or max) in O(1)
Any LIFO structure needing an O(1) aggregate (min/max) that must roll back on pop
Design problems where 'support operation X in O(1)' is the explicit constraint

Choose another pattern when

You need min over an arbitrary range, not the whole stack → segment tree / sparse table
Min over a sliding window (FIFO) → monotonic deque, not a min stack
You only ever read the min once at the end → just compute it then; no auxiliary structure

Interview takeaway

Carry the answer with the data: storing the running minimum at each stack level makes pop automatically undo it, trading O(n) extra space for O(1) queries. This 'remember the aggregate per level' idea also builds a queue from two stacks and underpins the two-stack max/min trick.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternStack design with an O(1) auxiliary aggregate. Recognise it when a LIFO structure must also answer min/max in constant time: store the aggregate per level so push maintains it and pop restores it. Related to two-stack queue and max-stack designs.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Implement Queue using Stacks
Coming soon
Two stacks (in/out) give amortized O(1) FIFO — same 'carry state across stacks' idea.
Max Stack
Coming soon
Symmetric to Min Stack, but popMax needs a more elaborate structure (e.g. balanced BST + stack).
Implement Stack using Queues
Coming soon
The reverse design exercise; one queue with rotation, or two queues.
Valid Parentheses
The canonical 'plain stack' problem this design extends.

Same pattern

←

Valid Parentheses

Continue · Next problem

Evaluate Reverse Polish Notation

mediumStack QueueLC #155Frequently asked

Min Stack

LCPractice

Stack & Queue · 2 of 17 · 9 min

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

In plain English

Examples

Example 1

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: [-3, 0, -2]
Note: getMin → -3 (min of {-2,0,-3}); pop removes -3; top → 0; getMin → -2 (min restored to before -3 was pushed).

Example 2

Input: push(2), push(2), getMin(), pop(), getMin()
Output: [2, 2]
Note: Duplicates: min stack holds [2,2]; popping one still leaves a 2 → getMin stays 2.

Example 3

Input: push(5), getMin(), top()
Output: [5, 5]
Note: Single element is both the top and the minimum.

Constraints

-2³¹ ≤ val ≤ 2³¹ − 1
pop, top and getMin are always called on non-empty stacks
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin

Clarifying questions4First question: Are pop/top/getMin ever called on an empty stack?Explore questions

Q1.Are pop/top/getMin ever called on an empty stack?
The constraints guarantee they aren't, so I don't need to throw — but I'll still handle the empty case correctly on the first push.
Q2.Can values be negative or duplicated?
Yes, the full int range and duplicates. Using <= vs < only matters for the space-optimized variant; the parallel-stack version handles duplicates trivially.
Q3.Does getMin remove the minimum or just report it?
Just reports it — it's a peek. The minimum only leaves when the element holding it is popped.
Q4.Is extra O(n) space acceptable for O(1) min?
Yes — the standard solution uses an auxiliary stack of the same size. If asked to reduce it, I'd store the min only when it changes, or encode deltas against the running min.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can design a data structure that maintains an O(1) auxiliary query under pushes and pops — specifically, how popping rolls back the minimum without recomputation.

Where candidates slip

Storing a single 'min' variable that can't be restored after the minimum is popped, or scanning the stack for getMin() (O(n)).

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Single Min Variable / Scan on getMin (Baseline)	`O(1) push/pop/top, O(n) getMin`	`O(n)`	Mention to expose why the naive idea breaks under pop, motivating the auxiliary stack.	Read
2	Parallel Min Stack (Optimal)Optimal	`O(1) for all operations`	`O(n)`	The answer they want. Lead with 'store the running min at each level so pop restores it for free'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Single Min Variable / Scan on getMin (Baseline)

TimeO(1) push/pop/top, O(n) getMinSpaceO(n)

Mention to expose why the naive idea breaks under pop, motivating the auxiliary stack.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The easy part is push/pop/top on a normal stack. What goes wrong if you keep just one variable for the current minimum?

2Hint 2Explore hint

A lone min variable can't tell you what the minimum was BEFORE the current min was pushed — once you pop it, the previous min is lost.

3Hint 3Explore hint

You could rescan the whole stack for getMin instead, but that's O(n) and violates the requirement.

A · Core idea

Use a normal stack and either (a) keep one min field, or (b) scan the stack on each getMin.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

push(5), push(1), pop(), getMin()

push(5)

min = 5

Statemin=5

Final resultincorrect

C · Code with teaching comments

Reference implementation previewclass MinStackNaive { private Deque<Integer> stack = new ArrayDeque<>(); private int min = Integer.MAX_VALUE; public void push(int val) {Explore the full code

solution.javaJava

Single Min Variable / Scan on getMin (Baseline) — reference

2 teaching notes

1
class MinStackNaive {
2
    private Deque<Integer> stack = new ArrayDeque<>();
3
    private int min = Integer.MAX_VALUE;
4
 
5
    public void push(int val) {
6
        stack.push(val);
7
        // Captures the new min but discards the old one — irreversible.
8
        min = Math.min(min, val);   // can't be undone on pop
9
    }
10
 
11
    public void pop() {
12
        stack.pop();                // min is now possibly stale
13
    }
14
 
15
    public int top() { return stack.peek(); }
16
 
17
    // Returns a stale minimum once the true min has been popped.
18
    public int getMin() { return min; }   // WRONG after pops
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(1) push/pop/top, O(n) getMin timeO(n) spaceOpen the invariant and proofExplore the proof

The minimum is a stack-structured quantity itself — it changes and must be undone in LIFO order exactly like the data. That's the clue that the minimum belongs on its own stack.

ComplexityO(1) push/pop/top, O(n) getMin time, O(n) space — A single min variable can't be restored on pop; recomputing min by scanning is O(n) per call.

E · Edge cases and pitfalls2A single min variable cannot recover the previous minimum after a pop.Explore edge cases

Pitfalls

A single min variable cannot recover the previous minimum after a pop.
Rescanning the stack for getMin is correct but O(n), breaking the constraint.

03.2

Approach 2 of 2 · Optimal

Parallel Min Stack (Optimal)

TimeO(1) for all operationsSpaceO(n)

The answer they want. Lead with 'store the running min at each level so pop restores it for free'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The minimum changes in LIFO order just like the data does. What structure naturally undoes its most recent change first?

2Hint 2Explore hint

Keep a second stack the same height as the main one; at each level store the minimum of all elements at or below that level.

3Hint 3Explore hint

On push, push min(val, currentMin). On pop, pop both. getMin is the top of the min stack — O(1).

A · Core idea

Maintain two stacks: stack for the values and mins where each entry is the minimum of all elements at or below that position.

top() and getMin(). Both are O(1) peeks: top() reads the top of stack, getMin() reads the top of mins.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Array state

push(-2)

stack & mins gain -2

min ↓

-2

[0]

Current pointerResolved stateNot processed

Final resultgetMin=-3, top=0, getMin=-2

C · Code with teaching comments

solution.javaJava

Parallel Min Stack (Optimal) — optimal

7 teaching notes

1
class MinStack {
2
    // Holds the actual values; ArrayDeque is the modern stack in Java.
3
    private final Deque<Integer> stack = new ArrayDeque<>();
4
    // Parallel stack: each entry is the min at or below its level.
5
    private final Deque<Integer> mins = new ArrayDeque<>();
6
 
7
    public MinStack() {
8
    }
9
 
10
    public void push(int val) {
11
        // Standard push of the value.
12
        stack.push(val);
13
        // First push → val is its own min; otherwise compare with the running min.
14
        int currentMin = mins.isEmpty() ? val : Math.min(val, mins.peek());
15
        // Keep mins the same height as stack so they pop together.
16
        mins.push(currentMin);
17
    }
18
 
19
    public void pop() {
20
        stack.pop();
21
        mins.pop();
22
    }
23
 
24
    public int top() {
25
        return stack.peek();
26
    }
27
 
28
    public int getMin() {
29
        // getMin is just the top of the min stack — O(1).
30
        return mins.peek();
31
    }
32
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.32 lines

D · Why it works and complexityO(1) for all operations timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls8push(5) then getMin/top — First push: mins empty → currentMin = 5. getMin and top both return 5.Explore edge cases

Edge cases handled

push(5) then getMin/topFirst push: mins empty → currentMin = 5. getMin and top both return 5.
push(2), push(2), pop(), getMin()mins = [2, 2]; popping leaves [2] → getMin stays 2 (duplicates handled).
all negatives, e.g. push(-1), push(-5)min(-5, -1) = -5 pushed → getMin returns -5; signs irrelevant.
push then pop down to empty, then push againmins empties with stack; next push treats val as its own min — no stale state.

Pitfalls

Popping only one of the two stacks — they desync and getMin lies.
On the first push, calling mins.peek() on an empty stack — guard with isEmpty().
Storing only when val < currentMin without the matching conditional pop — under-pops the min stack.
Recomputing min by scanning instead of peeking — silently O(n).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass MinStack { private final Deque<Integer> stack = new ArrayDeque<>(); private final Deque<Integer> mins = new ArrayDeque<>(); public MinStack() {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Desynced stacks on pop

The two stacks must stay the same height. Popping only the value stack leaves a stale entry on the min stack, so getMin reports a minimum that's no longer present.

Explore the code comparison

Don't write this

public void pop() {
    stack.pop();   // forgot mins.pop()
}

Write this instead

public void pop() {
    stack.pop();
    mins.pop();
}

Peeking an empty min stack on first push

On the very first push there is no current minimum yet. Calling mins.peek()/mins[-1] throws or errors. Treat the first value as its own minimum.

Explore the code comparison

Don't write this

def push(self, val):
    self.stack.append(val)
    self.mins.append(min(val, self.mins[-1]))  # IndexError when empty

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Auxiliary min stack tracking the minimum per level

Code pattern to memorize

push(x):  stack.push(x); mins.push(min(x, mins.peek() if mins else x))
pop():    stack.pop(); mins.pop()
top():    return stack.peek()
getMin(): return mins.peek()

Rules to remember

1Push to both stacks on every push, and pop from both on every pop — keep them the same height.
2The value pushed onto the min stack is min(newValue, currentMin), so each level remembers the minimum of everything below it.
3getMin() and top() are pure peeks — O(1), no scanning.
4Popping the min stack automatically restores the previous minimum; that's why you never need to recompute it.
5Handle the empty case on the first push (no current min yet) — the first value is its own minimum.

Use this pattern when

A stack that must also report its min (or max) in O(1)
Any LIFO structure needing an O(1) aggregate (min/max) that must roll back on pop
Design problems where 'support operation X in O(1)' is the explicit constraint

Choose another pattern when

You need min over an arbitrary range, not the whole stack → segment tree / sparse table
Min over a sliding window (FIFO) → monotonic deque, not a min stack
You only ever read the min once at the end → just compute it then; no auxiliary structure

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Implement Queue using Stacks
Coming soon
Two stacks (in/out) give amortized O(1) FIFO — same 'carry state across stacks' idea.
Max Stack
Coming soon
Symmetric to Min Stack, but popMax needs a more elaborate structure (e.g. balanced BST + stack).
Implement Stack using Queues
Coming soon
The reverse design exercise; one queue with rotation, or two queues.
Valid Parentheses
The canonical 'plain stack' problem this design extends.

Same pattern

←

Valid Parentheses

Continue · Next problem

Evaluate Reverse Polish Notation