21. Min Stack

Q: Why a parallel stack instead of storing (val, currentMin) pairs?

Same space. Slightly more cache-coherent. But the parallel-array form generalizes to a max stack and beyond.

Q: Optimization: when is it safe to skip pushing to minStack?

Push only when val < current min. On pop, decrement only if you're popping the current min value. Saves space when the input is mostly ascending.

easyAsked at Reddit

Design a stack that supports push, pop, top, and getMin in O(1). Reddit uses this to test data-structure design — the same auxiliary-state pattern they use to maintain hottest-comment-so-far while streaming an active comment thread.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Reddit loops.

Glassdoor (2026-Q1)— Reddit infra phone screen.
Blind (2025-12)— Reported on Reddit comments-team rounds as a design warm-up.

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: push(val), pop(), top(), getMin().

Constraints

-2^31 <= val <= 2^31 - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Examples

Example 1

Input

["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Approaches

1. Recompute min on getMin

Single array as stack. getMin scans entire stack.

Time: O(1) push/pop, O(n) getMin
Space: O(n)

class MinStack {
  constructor() { this.stack = []; }
  push(v) { this.stack.push(v); }
  pop() { this.stack.pop(); }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return Math.min(...this.stack); }
}

Tradeoff: Fails the constant-time getMin requirement.

2. Parallel min stack (optimal)

Maintain a second stack that holds the running min. Push min(val, current min) on every push. Pop in lockstep.

Time: O(1) all ops
Space: O(n)

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

Tradeoff: Constant time per op, 2x memory. Trade memory for time — typical Reddit infra trade-off.

Reddit-specific tips

Reddit interviewers expect you to discuss the memory trade-off. Bonus signal: mention an optimization — only push to minStack when val <= current min, and track count for duplicates. Saves space when values are mostly increasing.

Common mistakes

Pushing Math.min instead of the new value to the main stack.
Forgetting to push to minStack on first push (empty case).
Comparing values without handling negative numbers carefully (Math.min handles this fine).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

Implement Max Stack with O(1) max — same pattern.
Implement Queue with O(1) min/max — needs deque.
Sliding window minimum (LC 239).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.