Skip to main content

20. Min Stack

easyAsked at Vercel

Design a stack that supports push, pop, top, and getMin in O(1). Vercel asks this because the auxiliary-stack pattern is the same shape they use to track the lowest-cost deployment plan at every point in a rolling release.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel screen; the O(1) getMin is the bonus signal.
  • Blind (2026-Q1)— Reported in Vercel platform onsite recap.

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack() initializes the stack object; push(val) pushes the element val; pop() removes the element on the top; top() gets the top element; getMin() retrieves the minimum.

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.

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. Linear scan getMin

Standard stack; getMin walks the stack to find the min.

Time
push/pop/top O(1), getMin O(n)
Space
O(n)
class MinStack {
  constructor() { this.s = []; }
  push(v) { this.s.push(v); }
  pop() { this.s.pop(); }
  top() { return this.s[this.s.length - 1]; }
  getMin() { return Math.min(...this.s); }
}

Tradeoff: Violates the O(1) getMin requirement. Mention only to motivate the auxiliary stack.

2. Parallel min-stack (optimal)

Keep an auxiliary stack of running minimums. On push, also push min(val, current min). On pop, pop both.

Time
O(1) per op
Space
O(n)
class MinStack {
  constructor() {
    this.s = [];
    this.mins = [];
  }
  push(v) {
    this.s.push(v);
    const m = this.mins.length === 0 ? v : Math.min(v, this.mins[this.mins.length - 1]);
    this.mins.push(m);
  }
  pop() {
    this.s.pop();
    this.mins.pop();
  }
  top() { return this.s[this.s.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

Tradeoff: O(1) on every operation. The space cost is 2x but constant per element. A variant stores diffs to save space when many pushes don't change the min.

Vercel-specific tips

Vercel grades the O(1) getMin. They want the parallel-stack approach. Bonus signal: offering the diff-based optimization (only push to the mins stack when the new value is <= current min, requires careful pop logic). Articulate the trade-off.

Common mistakes

  • Using a single number to track current min — fails when the min is popped.
  • Forgetting to pop both stacks on pop() — stacks drift out of sync.
  • Computing min on every getMin via Math.min — O(n) and defeats the purpose.

Follow-up questions

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

  • Max stack (symmetric).
  • MinStack with O(1) getMedian — much harder, needs two heaps.
  • Implement using only one stack — encode pairs (val, currentMin).

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 does a single 'currentMin' variable not work?

When you pop the current min, you lose the second-smallest. You'd have to rescan the entire stack — O(n). The parallel stack remembers the history of mins.

How would the diff-based version save space?

Only push to the mins stack when val <= currentMin. On pop, if the popped value equals currentMin, also pop mins. Saves space when the input has long runs without new mins.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →