LeetCode · #155

Min Stack Solution

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #155

🏗️

Pattern

Design — auxiliary min stack

Design a stack class MinStack that supports: push(val) — push element onto stack, pop() — remove top element, top() — get top element, getMin() — retrieve the minimum element. Each operation must run in O(1) time.

Example

 MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // → -3
minStack.pop();
minStack.top(); // → 0
minStack.getMin(); // → -2 

Constraints

 • -2³¹ ≤ val ≤ 2³¹ - 1 • pop, top, getMin called on non-empty stacks • At most 3 × 10⁴ calls total 

Section Two · Approach 1

Brute Force — Scan for Min O(n)

Use a regular stack. For getMin(), scan the entire stack to find the minimum. Push, pop, and top are O(1), but getMin is O(n).

Problem: getMin scans every element. By maintaining a second stack that tracks the running minimum, we get O(1) for all operations.

Operation	Time
push / pop / top	O(1)
getMin	O(n) — scans stack

Section Three · Approach 2

Two Stacks — O(1) All Operations

Maintain two stacks: a main stack for normal operations and a min stack that mirrors it, always holding the current minimum at the top. On push, push to main stack and push min(val, minStack.top) to the min stack. On pop, pop from both.

💡 Mental model: Imagine two columns of sticky notes. The left column stores actual values. At the same height on the right column, you write "the smallest value in the left column from this point down." Every time you add or remove from the left, you update the right accordingly. Reading the minimum is just glancing at the top of the right column.

Algorithm

push(val): Push val onto main. Push min(val, minStack.peek()) onto minStack.
pop(): Pop from both stacks.
top(): Return main stack's top.
getMin(): Return minStack's top — always the current min.

🎯 Why it works:

The min stack is synchronized with the main stack.
Its top always reflects the minimum of all elements currently in main.
When we pop from main, the next element's minimum is already stored in minStack — no recomputation needed.

Section Four · Trace

Visual Walkthrough

Trace: push(-2), push(0), push(-3), getMin(), pop(), getMin():

Two Stacks — main + min tracking

Section Five · Implementation

Code — Java & Python

Java — Two Stacks

 import java.util.Stack;
class MinStack {
private Stack<Integer> main = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
public void push(int val) {
        main.push(val);
int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
        minStack.push(currentMin);
    }
public void pop() {
        main.pop();
        minStack.pop();
    }
public int top() {
return main.peek();
    }
public int getMin() {
return minStack.peek(); // O(1) — always current min
}
}

Python — Two Stacks

 class MinStack:
def __init__(self):
        self.main = []
        self.min_stack = []
def push(self, val: int) -> None:
        self.main.append(val)
        curr_min = min(val, self.min_stack[-1]) if self.min_stack else val
        self.min_stack.append(curr_min)
def pop(self) -> None:
        self.main.pop()
        self.min_stack.pop()
def top(self) -> int:
return self.main[-1]
def getMin(self) -> int:
return self.min_stack[-1]

Section Six · Analysis

Complexity Analysis

Approach	push/pop/top	getMin	Space
Single stack + scan	O(1)	O(n)	O(n)
Two Stacks ← optimal	O(1)	O(1)	O(n) — double memory

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Scenario	Why It Matters
Single element	push(5), getMin()	Min is the only element → 5.
Duplicate mins	push(1), push(1), pop()	Both min entries are 1. After pop, min is still 1.
New min then pop	push(3), push(1), pop()	Min reverts to 3 after popping 1. MinStack handles this automatically.
Large negatives	push(-2³¹)	Integer.MIN_VALUE works — no overflow in min comparison.

⚠ Common Mistake: Only pushing to the min stack when the value is a new minimum. This breaks on pop — if the minimum value is popped, the min stack is shorter than the main stack and falls out of sync. Always push to both stacks on every push, and pop from both on every pop.

← Back to Stack problems

LearningTree

LC 155 · Min Stack — Solution & Explanation | DSA Guide