Skip to main content

20. Min Stack

easyAsked at Ola

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

By Alex Chen, 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.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 3 * 10^4 calls per method
  • pop, top, getMin only on non-empty stacks

Examples

Example 1

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

Approaches

1. Scan on getMin

Use a single array and scan it for 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 a second stack of running minimums updated on push and pop; getMin returns its top.

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(this.m[this.m.length-1], x) : 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:

Ola-specific tips

Ola tests this to see if you carry auxiliary state cleanly; relate it to tracking running min surge multiplier across an event-sourced ride log.

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

Practice these live with InterviewChamp.AI →