20. Min Stack

Q: 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.

Q: 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.

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 Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

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.