155. Min Stack

Design a stack that supports push, pop, top and retrieving the minimum element, all in constant time. Input is a LeetCode-style list of operations.

Store each value together with the minimum of the stack at the moment it was pushed. The top pair always knows the current minimum.

1class MinStack {
2  s: [number, number][] = [];
3  push(val: number): void {
4    const min = this.s.length ? Math.min(val, this.s.at(-1)![1]) : val;
5    this.s.push([val, min]);
6  }
7  pop(): void { this.s.pop(); }
8  top(): number { return this.s.at(-1)![0]; }
9  getMin(): number { return this.s.at(-1)![1]; }
10}

op = MinStack()

stack (value | min so far)

empty

output

null

Empty stack.

1 / 0

Space: play/pause · ←/→: step