155. Min Stack

Quick Identifier

Topic: stack
Pattern: Stack + auxiliary min history
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Microsoft
Frequency: High
LeetCode: 155

Quick Sights

Time Complexity: O(1) from the optimal approach.
Space Complexity: See optimal approach. from the optimal approach.
Core Mechanism: Design a stack supporting push, pop, top, and getMin in amortized O(1) per operation. pop and top follow normal stack behavior.

Concept Explanation

Design a stack supporting push, pop, top, and getMin in amortized O(1) per operation. pop and top follow normal stack behavior.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

"Min in constant time" alongside stack ops
Duplicate minimum values matter — track counts or store pairs (value, currentMin)
Second stack of mins or store (x, minAfterPush)

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — scan entire stack for min — O(n) per getMin.
Better — heap — breaks LIFO pairing unless augmented.
Optimal — O(1) push/pop/min — parallel min-stack storing minimum snapshot per depth.

Optimal Solution

Go

type MinStack struct {
	values   []int
	minStack []int
}

func Constructor() MinStack {
	return MinStack{
		values:   []int{},
		minStack: []int{},
	}
}

func (stack *MinStack) Push(val int) {
	stack.values = append(stack.values, val)
	if len(stack.minStack) == 0 || val <= stack.minStack[len(stack.minStack)-1] {
		stack.minStack = append(stack.minStack, val)
	}
}

func (stack *MinStack) Pop() {
	top := stack.values[len(stack.values)-1]
	stack.values = stack.values[:len(stack.values)-1]
	if top == stack.minStack[len(stack.minStack)-1] {
		stack.minStack = stack.minStack[:len(stack.minStack)-1]
	}
}

func (stack *MinStack) Top() int {
	return stack.values[len(stack.values)-1]
}

func (stack *MinStack) GetMin() int {
	return stack.minStack[len(stack.minStack)-1]
}

JavaScript

class MinStack {
	constructor() {
		this.values = [];
		this.minValues = [];
	}
	push(value) {
		this.values.push(value);
		const priorMin = this.minValues.at(-1);
		if (this.minValues.length === 0 || value <= priorMin) {
			this.minValues.push(value);
		}
	}
	pop() {
		const top = this.values.pop();
		if (top === this.minValues.at(-1)) {
			this.minValues.pop();
		}
	}
	top() {
		return this.values.at(-1);
	}
	getMin() {
		return this.minValues.at(-1);
	}
}