155. Min Stack

At a Glance

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

Problem (one-liner)

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

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)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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);
	}
}