Skip to main content

20. Min Stack

easyAsked at Lyft

Design a stack that supports getMin in constant time.

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

Problem

Design a stack supporting push, pop, top, and a getMin operation that all run in constant time. Implement push, pop, top, and getMin.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top, and getMin always called on a non-empty stack
  • At most 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(2), push(1), getMin(), pop(), getMin()
Output
[1, 2]

Approaches

1. Recompute min on getMin

Scan whole stack to find min.

Time
O(n) per getMin
Space
O(n)
this.stack=[]; push(x){this.stack.push(x);} pop(){this.stack.pop();}
getMin(){return Math.min(...this.stack);}

Tradeoff:

2. Two stacks — values + running min

Auxiliary stack stores running minimum so getMin is O(1).

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

Tradeoff:

Lyft-specific tips

Lyft uses this design pattern in their pricing-evaluator service — they want to see the auxiliary stack approach and care about correctness under concurrent push/pop sequences.

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

Practice these live with InterviewChamp.AI →