Skip to main content

7. Min Stack

easyAsked at Byju's

Design a stack supporting push, pop, top, and O(1) minimum retrieval.

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

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class with push(val), pop(), top(), and getMin() methods. All operations must run in O(1) time.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • Methods are called only on non-empty stacks for pop/top/getMin

Examples

Example 1

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

Example 2

Input
push(1), push(2), getMin(), pop(), getMin()
Output
1, null, 1

Approaches

1. Linear scan for min

Recompute the minimum each call to getMin by scanning the stack.

Time
O(n) per getMin
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:

2. Parallel min stack

Maintain a second stack of running minimums in lockstep. Each push records the smaller of the new value and current min.

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

Tradeoff:

Byju's-specific tips

Byju's video-tutoring style rewards designs you can whiteboard for a learner, so draw the parallel-min-stack invariant before writing the class.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Byju's coding interview questions

See all Byju's problems →

Companies that also ask Min Stack