Skip to main content

20. Min Stack

easyAsked at Slack

Design a stack with constant-time minimum lookup.

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

Problem

Design a stack supporting push, pop, top, and getMin in O(1) time. All operations must be constant time.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • pop, top, getMin called only on non-empty stack
  • 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(1), top(), getMin()
Output
1, 1

Approaches

1. Scan on getMin

Single array; recompute min by scanning on every getMin.

Time
O(n) per getMin
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 an auxiliary stack of running minimums. Push min(x, top of min) on each push.

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 ? Math.min(x, this.m[this.m.length - 1]) : x);
  }
  pop() { this.s.pop(); this.m.pop(); }
  top() { return this.s[this.s.length - 1]; }
  getMin() { return this.m[this.m.length - 1]; }
}

Tradeoff:

Slack-specific tips

Slack uses similar auxiliary-state patterns for unread-count tracking — they want you to articulate the space-time tradeoff out loud.

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

Practice these live with InterviewChamp.AI →