Stack crash course ↗ · 17

155. Min Stack

Design a stack that supports push, pop, top, and getMin — all in O(1). The trick: maintain a parallel min-stack so the current minimum is always one peek away.

● MediumStackDesignAuxiliary Data StructureTypeScript

PROBLEM What we're solving

Implement a stack class with four O(1) operations: push(val), pop(), top(), and getMin(). The first three are standard; the challenge is getMin()— it must return the minimum element currently in the stack in constant time, without scanning the whole stack.

Worked example:

push(5) → stack: [5]
push(3) → stack: [5, 3]
push(7) → stack: [5, 3, 7]
getMin() → 3
top() → 7
pop() → stack: [5, 3]
getMin() → 3 (still correct after pop)

KEY IDEA A parallel min-stack tracks the running minimum

Insight → at every stack level, record what the minimum was at that moment. Use a second stack (minStack) that mirrors the main stack — each slot stores min(val, minStack.top). When you pop the main stack, pop minStack too. The minimum is always at minStack.top, so getMin() is a single peek. No scanning, no heap, no sorting — just two stacks moving in lockstep.

RECIPE Lock-step push and pop, instant min

0 · Two stacks. Maintain stack (normal values) and minStack (running minimums). They always have the same length.
1 · push(val). Append val to stack. Append min(val, minStack.top) to minStack (or just valif it's the first element). This records the minimum that would be correct if we stopped here.
2 · pop(). Pop both stacks. The minimum stored for the discarded level is discarded too, so minStack.topautomatically reflects the new state.
3 · top(). Return stack.top — standard peek.
4 · getMin(). Return minStack.top — O(1) peek of the pre-computed running minimum.

Classic confusion → only pushing to minStack when the new value is less than or equal to the current min (to save space). This works but breaks if the same minimum value appears twice — when you pop one copy, the second copy in minStack is also gone and future getMin() calls return the wrong answer. The simplest fix is to always push to both stacks, sacrificing a little space for correctness without special-casing.

COST Complexity & alternatives

Scan on getMin

O(n) getMin

Simple but linear — unusable if getMin is called often.

Auxiliary min-stack

O(1) all ops

O(n) extra space; every op is a constant-time peek or append.

Space note

The parallel stack doubles memory from O(n) to O(2n) — still O(n). The "push only on new min" optimization reduces minStack size in the best case but requires careful handling of duplicate minimums. For interviews, stick to the always-push version unless asked to optimize space.

Pattern transfer →the same "parallel auxiliary structure tracks a derived property" idea appears in Max Stack (mirror this solution with max), Sliding Window Maximum (monotonic deque instead of a second stack), Stock Span Problem, and any "O(1) query on a stack slice" variant.

RUN IT Min Stack — push/pop/top/getMin all O(1)

Operations:

step 0 / 8

STARTBoth stacks empty. Each push records value + running minimum.

1▶class MinStack {
2▶  private stack: number[] = [];
3▶  private minStack: number[] = [];
4 
5  push(val: number): void {
6    this.stack.push(val);
7    const curMin = this.minStack.length === 0
8      ? val
9      : Math.min(val, this.minStack[this.minStack.length - 1]);
10    this.minStack.push(curMin);
11  }
12 
13  pop(): void {
14    this.stack.pop();
15    this.minStack.pop();
16  }
17 
18  top(): number {
19    return this.stack[this.stack.length - 1];
20  }
21 
22  getMin(): number {
23    return this.minStack[this.minStack.length - 1];
24  }
25}

State

(empty)

stack

(empty)

minStack

stack toprunning minimumreturned value

slowfast

TYPESCRIPT The solution, annotated

minStack.ts
class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

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

  pop(): void {
    this.stack.pop();
    this.minStack.pop();
  }

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

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

Reading it block by block

Lines 2–3 — two parallel arrays. stack holds the real values. minStack holds one number per level: the minimum of everything in stack up to and including that slot. Both arrays grow and shrink together.

Lines 5–11 — push. Append val to stack. For minStack, compute min(val, minStack.top)— "what's the smallest thing in the stack right now?" — and append that. This is the pre-computation that makes getMin O(1) later.

Lines 13–16 — pop. Remove the last element from both stacks. Because the minimum for the just-removed level is also discarded, minStack.topautomatically becomes the correct minimum for the remaining elements. No recomputation needed.

Lines 18–20 — top. Peek the last element of stack. Standard O(1) array access.

Lines 22–24 — getMin. Peek the last element of minStack. It already holds the running minimum by construction — O(1) and correct at every stack level.

Complexity → All four operations are O(1) time. Space is O(n) for the main stack plus O(n) for the auxiliary min-stack — O(n) overall. The min-stack stores at most one entry per push, so it never exceeds the size of the main stack.

INTERVIEWFollow-ups they'll ask

"Can you reduce the space used by minStack?" Yes — only push to minStack when the new value is <= current min. But then on pop you must only pop minStack when the popped value equals the current min. This is trickier — know both variants.
"What if we need a Max Stack instead?" Replace Math.min with Math.max — the structure is identical. LeetCode 716 asks exactly this.
"What about a stack that supports getMin and pop-min?"That's harder — you need a sorted structure (like a heap + lazy deletion) for O(log n) pop-min while keeping push/pop O(log n) as well.
"Instead of two stacks, can we store pairs?" Yes: store [val, curMin] tuples in a single stack. Same O(n) space and O(1) ops, just different packaging.
"What are the edge cases?" Calling pop, top, or getMin on an empty stack is undefined by the problem constraints — but know to guard against it in production.

OPTIMAL Stack

minStack.ts
class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

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

  pop(): void {
    this.stack.pop();
    this.minStack.pop();
  }

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

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

ALT 1 Brute force — rescan the stack on getMin

O(1) push/pop/top · O(n) getMin · O(n) space

Drop the parallel min-stack entirely: keep just one stack and, whenever getMin is called, walk the whole stack to find the smallest value. A clean correctness baseline before you cache the running minimum.

approach-2.ts
class MinStack {
  private stack: number[] = [];

  push(val: number): void {
    this.stack.push(val);
  }

  pop(): void {
    this.stack.pop();
  }

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

  getMin(): number {
    // Linear scan every time — no auxiliary structure.
    let min = Infinity;
    for (const v of this.stack) {
      if (v < min) min = v;
    }
    return min;
  }
}

Note → Correct, but each getMinis O(n). A workload that queries the minimum after every operation degrades to O(n²) overall. The parallel min-stack trades a little extra memory to make getMin O(1).

MNEMONIC The one-liner

"Two stacks march in lockstep — the second one always remembers the lowest point so far."

TRIGGERS When you see _ → reach for _

"getMin in O(1)" alongside push/pop	parallel minStack, always push both
stack + query on a derived property (min/max)	auxiliary stack tracking that property
O(1) range-min/max on a growing prefix	running min/max stored per level
"design a data structure" with constant-time queries	augment the structure with a companion stack/array

SKELETON The reusable shape

skeleton.ts
class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];

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

FLASHCARDS Tap to flip

How does a Min Stack achieve O(1) getMin?

A parallel minStack stores min(val, prevMin) at each level. getMin() is just minStack.top.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

After push(5), push(3), push(7): what does getMin() return?

QUESTION 02

What is stored in minStack at each level?

QUESTION 03

Why must you always push to minStack, not only when val <= curMin?

QUESTION 04

What is the time complexity of all four operations (push, pop, top, getMin) in the auxiliary min-stack solution?

QUESTION 05

push(5), push(3), pop(), getMin() — what does getMin() return?

QUESTION 06

The "store [val, curMin] pairs" variant differs from the two-stack approach in what way?

QUESTION 07

Which sibling problem uses an analogous "auxiliary structure tracks a property" idea with a deque instead of a stack?

QUESTION 08

#155 · Min StackAn auxiliary min-stack (or per-entry (value, currentMin) pair) keeps the running minimum in sync with every push and pop, so getMin is O(1) alongside push, pop, and top.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA A parallel min-stack tracks the running minimum

RECIPE Lock-step push and pop, instant min

COST Complexity & alternatives

Space note

RUN IT Min Stack — push/pop/top/getMin all O(1)

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Stack

ALT 1 Brute force — rescan the stack on getMin

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _