Skip to main content

7. Min Stack

easyAsked at Rappi

Design a stack that supports push, pop, top, and retrieving the minimum in constant time — Rappi frames this as tracking the lowest-ETA candidate in a dispatch queue without rescanning.

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

Problem

Implement a class MinStack with push(x), pop(), top(), and getMin() — every operation must run in O(1) time.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • All methods must be O(1)

Examples

Example 1

Input
push(-2), push(0), push(-3), getMin()
Output
-3

Example 2

Input
pop(), top(), getMin()
Output
0, -2

Approaches

1. Rescan on getMin

Store values in a normal stack and scan all elements on each getMin call.

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.at(-1); }
  getMin() { return Math.min(...this.s); }
}

Tradeoff:

2. Paired min stack

Maintain a parallel stack whose top always holds the running minimum, updated on every push and pop.

Time
O(1)
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.at(-1)) : x); }
  pop() { this.s.pop(); this.m.pop(); }
  top() { return this.s.at(-1); }
  getMin() { return this.m.at(-1); }
}

Tradeoff:

Rappi-specific tips

Rappi will explicitly test that getMin stays O(1) under spike load — the paired-stack invariant is the standard answer their dispatch service uses for lowest-ETA tracking.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More Rappi coding interview questions

See all Rappi problems →

Companies that also ask Min Stack