Skip to main content

21. Min Stack

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 Alex Chen, Founder, InterviewChamp.AI · Last verified

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.

Output

Press Run or Cmd+Enter to execute

FAQ

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.

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.

Practice these live with InterviewChamp.AI

Drill Min Stack and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →