Skip to main content

8. Min Stack

easyAsked at Freshworks

Design a stack with O(1) push, pop, top, and getMin — Freshworks frames it as 'lowest open-ticket priority' at any point in an undo history.

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

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top, and getMin are only called on non-empty stacks
  • Up to 3 * 10^4 calls

Examples

Example 1

Input
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output
-3, _, 0, -2

Example 2

Input
push(5), push(3), getMin(), push(7), getMin()
Output
3, 3

Approaches

1. Brute force

Use a single array; on every getMin, scan the whole thing.

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

Tradeoff:

2. Parallel min stack

Keep a second stack that tracks the running minimum. On push, push min(newVal, currentMin). On pop, pop both.

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

Tradeoff:

Freshworks-specific tips

Freshworks expects the parallel-stack design, not the 'store pair' variant — they care about the invariant that mins[i] is always the min of stack[0..i] and will probe that.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →