Skip to main content

20. Min Stack

easyAsked at Zoom

Design a stack supporting push, pop, top, and getMin all in O(1).

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

Problem

Design a stack that supports push(x), pop(), top(), and retrieving the minimum element in constant time. All operations must be O(1).

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 3 * 10^4 operations

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(),pop(),getMin()
Output
3, -, 5

Approaches

1. Scan stack on getMin

O(n) scan whenever getMin is called.

Time
O(n) per getMin
Space
O(n)
getMin(){ return Math.min(...this.stack); }

Tradeoff:

2. Auxiliary min stack

Maintain a parallel stack that holds the running minimum.

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

Tradeoff:

Zoom-specific tips

Zoom uses min-stack patterns for tracking minimum bitrate across active streams — call out the analog to adaptive-bandwidth selection.

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 Zoom interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →