155. Min Stack (Medium)

Problem

Design a stack that supports push, pop, top, and getMin, all in $O(1)$ time.

Example

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

LeetCode 155 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, scan on getMin

Use a plain stack; compute min(stack) on every getMin call.

Python

class MinStack:
    def __init__(self):
        self.stack = []                            # L1: O(1)
    def push(self, val: int) -> None:
        self.stack.append(val)                     # L2: O(1) amortized
    def pop(self) -> None:
        self.stack.pop()                           # L3: O(1)
    def top(self) -> int:
        return self.stack[-1]                      # L4: O(1)
    def getMin(self) -> int:
        return min(self.stack)                     # L5: O(n) full scan

TypeScript

class MinStack {
    private stack: number[] = [];                          // L1: O(1)
    push(val: number): void { this.stack.push(val); }      // L2: O(1) amortized
    pop(): void { this.stack.pop(); }                      // L3: O(1)
    top(): number { return this.stack[this.stack.length - 1]; }  // L4: O(1)
    getMin(): number { return Math.min(...this.stack); }   // L5: O(n) full scan
}

Go

type MinStack struct {
    stack []int                                    // L1: O(1)
}

func Constructor() MinStack { return MinStack{} }

func (ms *MinStack) Push(val int) {
    ms.stack = append(ms.stack, val)               // L2: O(1) amortized
}
func (ms *MinStack) Pop() {
    ms.stack = ms.stack[:len(ms.stack)-1]          // L3: O(1)
}
func (ms *MinStack) Top() int {
    return ms.stack[len(ms.stack)-1]               // L4: O(1)
}
func (ms *MinStack) GetMin() int {
    m := ms.stack[0]
    for _, v := range ms.stack {                   // L5: O(n) full scan
        if v < m { m = v }
    }
    return m
}

Swift

final class MinStack {
    private var values: [Int] = []
    func push(_ value: Int) { values.append(value) }
    func pop() { values.removeLast() }
    func top() -> Int { values.last ?? 0 }
    func getMin() -> Int { values.min() ?? 0 }
}

Where the time goes, line by line

Variables: n = number of elements currently on the stack.

Line	Per-call cost	Times executed	Contribution
L2 (push)	$O(1)$ amortized	per call	$O(1)$ per push
L3 (pop)	$O(1)$	per call	$O(1)$ per pop
L4 (top)	$O(1)$	per call	$O(1)$ per top
L5 (getMin scan)	$O(n)$	per call	$O(n)$ per getMin ← bottleneck

min(stack) must scan all n elements every time.

Complexity

• push, pop, top: $O(1)$.
• getMin: $O(n)$.
• Space: $O(n)$.

Fails the problem’s $O(1)$ requirement for getMin.

Approach 2: Auxiliary min-stack

Maintain a parallel stack of running minimums. On push, push min(val, current_min) onto the aux stack; on pop, pop both.

Python

class MinStack:
    def __init__(self):
        self.stack = []                            # L1: O(1)
        self.mins = []                             # L2: O(1) parallel min-stack

    def push(self, val: int) -> None:
        self.stack.append(val)                     # L3: O(1)
        self.mins.append(val if not self.mins else min(val, self.mins[-1]))  # L4: O(1)

    def pop(self) -> None:
        self.stack.pop()                           # L5: O(1)
        self.mins.pop()                            # L6: O(1)

    def top(self) -> int:
        return self.stack[-1]                      # L7: O(1)

    def getMin(self) -> int:
        return self.mins[-1]                       # L8: O(1) top of min-stack

TypeScript

class MinStack {
    private stack: number[] = [];                  // L1: O(1)
    private mins: number[] = [];                   // L2: O(1) parallel min-stack

    push(val: number): void {
        this.stack.push(val);                      // L3: O(1)
        this.mins.push(this.mins.length === 0 ? val : Math.min(val, this.mins[this.mins.length - 1]));  // L4: O(1)
    }

    pop(): void {
        this.stack.pop();                          // L5: O(1)
        this.mins.pop();                           // L6: O(1)
    }

    top(): number { return this.stack[this.stack.length - 1]; }  // L7: O(1)

    getMin(): number { return this.mins[this.mins.length - 1]; } // L8: O(1) top of min-stack
}

Go

type MinStack struct {
    stack []int                                    // L1: O(1)
    mins  []int                                    // L2: O(1) parallel min-stack
}

func Constructor() MinStack { return MinStack{} }

func (ms *MinStack) Push(val int) {
    ms.stack = append(ms.stack, val)               // L3: O(1)
    if len(ms.mins) == 0 || val < ms.mins[len(ms.mins)-1] {
        ms.mins = append(ms.mins, val)             // L4: O(1)
    } else {
        ms.mins = append(ms.mins, ms.mins[len(ms.mins)-1])
    }
}
func (ms *MinStack) Pop() {
    ms.stack = ms.stack[:len(ms.stack)-1]          // L5: O(1)
    ms.mins = ms.mins[:len(ms.mins)-1]             // L6: O(1)
}
func (ms *MinStack) Top() int {
    return ms.stack[len(ms.stack)-1]               // L7: O(1)
}
func (ms *MinStack) GetMin() int {
    return ms.mins[len(ms.mins)-1]                 // L8: O(1) top of min-stack
}

Swift

final class MinStack {
    private var values: [Int] = []
    private var minimums: [Int] = []
    func push(_ value: Int) {
        values.append(value)
        if value <= (minimums.last ?? value) { minimums.append(value) }
    }
    func pop() {
        let removed = values.removeLast()
        if removed == minimums.last { minimums.removeLast() }
    }
    func top() -> Int { values.last ?? 0 }
    func getMin() -> Int { minimums.last ?? 0 }
}

Where the time goes, line by line

Variables: n = number of elements currently on the stack.

Line	Per-call cost	Times executed	Contribution
L3, L4 (push both stacks)	$O(1)$	per push	$O(1)$ per push
L5, L6 (pop both stacks)	$O(1)$	per pop	$O(1)$ per pop
L7 (top)	$O(1)$	per call	$O(1)$ per top
L8 (getMin)	$O(1)$	per call	$O(1)$ per getMin ← optimal

Every operation is $O(1)$; the mins stack mirrors every push/pop.

Complexity

• All operations: $O(1)$.
• Space: $O(n)$ + $O(n)$ = $O(n)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Single stack of (value, running_min) tuples (optimal, one container)

Same asymptotics as Approach 2 but with one container instead of two.

Python

class MinStack:
    def __init__(self):
        self.stack = []                            # L1: O(1) list of (value, running_min)

    def push(self, val: int) -> None:
        cur_min = val if not self.stack else min(val, self.stack[-1][1])  # L2: O(1)
        self.stack.append((val, cur_min))          # L3: O(1) amortized

    def pop(self) -> None:
        self.stack.pop()                           # L4: O(1)

    def top(self) -> int:
        return self.stack[-1][0]                   # L5: O(1) first element of top tuple

    def getMin(self) -> int:
        return self.stack[-1][1]                   # L6: O(1) second element of top tuple

TypeScript

class MinStack {
    private stack: [number, number][] = [];        // L1: O(1) [value, running_min]

    push(val: number): void {
        const curMin = this.stack.length === 0 ? val : Math.min(val, this.stack[this.stack.length - 1][1]);  // L2: O(1)
        this.stack.push([val, curMin]);             // L3: O(1) amortized
    }

    pop(): void { this.stack.pop(); }              // L4: O(1)

    top(): number { return this.stack[this.stack.length - 1][0]; }   // L5: O(1)

    getMin(): number { return this.stack[this.stack.length - 1][1]; } // L6: O(1)
}

Go

type frame struct {
    val    int
    curMin int
}

type MinStack struct {
    stack []frame                                  // L1: O(1) list of {val, curMin}
}

func Constructor() MinStack { return MinStack{} }

func (ms *MinStack) Push(val int) {
    curMin := val                                  // L2: O(1)
    if len(ms.stack) > 0 && ms.stack[len(ms.stack)-1].curMin < curMin {
        curMin = ms.stack[len(ms.stack)-1].curMin
    }
    ms.stack = append(ms.stack, frame{val, curMin}) // L3: O(1) amortized
}
func (ms *MinStack) Pop() {
    ms.stack = ms.stack[:len(ms.stack)-1]          // L4: O(1)
}
func (ms *MinStack) Top() int {
    return ms.stack[len(ms.stack)-1].val           // L5: O(1)
}
func (ms *MinStack) GetMin() int {
    return ms.stack[len(ms.stack)-1].curMin        // L6: O(1)
}

Swift

final class MinStack {
    private var entries: [(value: Int, minimum: Int)] = []
    func push(_ value: Int) { entries.append((value, min(value, entries.last?.minimum ?? value))) }
    func pop() { entries.removeLast() }
    func top() -> Int { entries.last?.value ?? 0 }
    func getMin() -> Int { entries.last?.minimum ?? 0 }
}

Where the time goes, line by line

Variables: n = number of elements currently on the stack.

Line	Per-call cost	Times executed	Contribution
L2, L3 (push: compute min + append tuple)	$O(1)$	per push	$O(1)$ per push
L4 (pop)	$O(1)$	per pop	$O(1)$ per pop
L5 (top)	$O(1)$	per call	$O(1)$ per top
L6 (getMin)	$O(1)$	per call	$O(1)$ per getMin ← optimal

All operations remain $O(1)$ by keeping the running minimum embedded in each stack frame.

Complexity

• All operations: $O(1)$.
• Space: $O(n)$.

Optional refinement: store only min-changes on a second stack

A third variant pushes to the aux min-stack only when a new minimum is established (and pops when popping a value equal to the current min). Saves memory on heavily-duplicated stacks. Same asymptotics.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	push/pop/top	getMin	Space
Scan on getMin	$O(1)$	$O(n)$	$O(n)$
Auxiliary min-stack	$O(1)$	$O(1)$	$O(n)$
Tuple stack	$O(1)$	$O(1)$	$O(n)$

The tuple-stack and auxiliary-stack approaches are equivalent in Big-O. Pick by taste.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_min_stack.py and run.
# Uses the canonical implementation (Approach 3: tuple stack).

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

    def push(self, val: int) -> None:
        cur_min = val if not self.stack else min(val, self.stack[-1][1])
        self.stack.append((val, cur_min))

    def pop(self) -> None:
        self.stack.pop()

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

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

def _run_tests():
    ms = MinStack()
    ms.push(-2)
    ms.push(0)
    ms.push(-3)
    assert ms.getMin() == -3
    ms.pop()
    assert ms.top() == 0
    assert ms.getMin() == -2

    # Push in increasing order
    ms2 = MinStack()
    ms2.push(1)
    ms2.push(2)
    ms2.push(3)
    assert ms2.getMin() == 1
    ms2.pop()
    assert ms2.getMin() == 1

    # Single element
    ms3 = MinStack()
    ms3.push(5)
    assert ms3.top() == 5
    assert ms3.getMin() == 5

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class MinStack {
    private stack: [number, number][] = [];
    push(val: number): void {
        const curMin = this.stack.length === 0 ? val : Math.min(val, this.stack[this.stack.length - 1][1]);
        this.stack.push([val, curMin]);
    }
    pop(): void { this.stack.pop(); }
    top(): number { return this.stack[this.stack.length - 1][0]; }
    getMin(): number { return this.stack[this.stack.length - 1][1]; }
}

const ms = new MinStack();
ms.push(-2); ms.push(0); ms.push(-3);
console.assert(ms.getMin() === -3);
ms.pop();
console.assert(ms.top() === 0);
console.assert(ms.getMin() === -2);

const ms2 = new MinStack();
ms2.push(1); ms2.push(2); ms2.push(3);
console.assert(ms2.getMin() === 1);
ms2.pop();
console.assert(ms2.getMin() === 1);

const ms3 = new MinStack();
ms3.push(5);
console.assert(ms3.top() === 5);
console.assert(ms3.getMin() === 5);
console.log('all tests pass');

Related data structures

• Stacks, carrying running aggregate state per frame is a classic pattern

Related concepts

• Stack Parsing, the last open, first closed model for nested syntax and reversible operations.
• Simulation, the explicit state model for executing rules exactly while keeping cases organized.