Skip to main content

9. Min Stack

easyAsked at Swiggy

Design a stack that returns the minimum element in O(1).

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Implement MinStack with push, pop, top, and getMin all running in O(1). Values are 32-bit signed integers.

Constraints

  • push, pop, top, getMin called <= 3 * 10^4 times
  • pop, top, getMin never called on empty stack

Examples

Example 1

Input
push(-2);push(0);push(-3);getMin();pop();top();getMin()
Output
-3, then -3 popped, top=0, getMin=-2

Example 2

Input
push(5);push(3);getMin();pop();getMin()
Output
3 then 5

Approaches

1. Scan on getMin

Plain array; getMin scans every call.

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

Tradeoff:

2. Parallel min stack

Maintain a second stack whose top is always the running minimum. Push onto it only when new value <= current min; pop in lockstep when top of main stack equals top of min stack.

Time
O(1) per op
Space
O(n)
class MinStack {
  constructor() { this.s = []; this.m = []; }
  push(x) {
    this.s.push(x);
    if (!this.m.length || x <= this.m[this.m.length - 1]) this.m.push(x);
  }
  pop() {
    const x = this.s.pop();
    if (x === this.m[this.m.length - 1]) this.m.pop();
    return x;
  }
  top() { return this.s[this.s.length - 1]; }
  getMin() { return this.m[this.m.length - 1]; }
}

Tradeoff:

Swiggy-specific tips

Swiggy interviewers like to see invariants verbalized — say out loud why pushing to the min stack only on <= keeps duplicates safe during pops.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Swiggy coding interview questions

See all Swiggy problems →

Companies that also ask Min Stack