Skip to main content

10. Min Stack

easyAsked at Flipkart

Design a stack with O(1) push, pop, top and getMin — Flipkart uses it to test whether candidates pick auxiliary structures over recomputation on every call.

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

Problem

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

Constraints

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top, getMin only called on non-empty stacks

Examples

Example 1

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

Example 2

Input
push(5), push(3), getMin(), pop(), getMin()
Output
3, (pop), 5

Approaches

1. Recompute min

Single stack; scan for min on each getMin call.

Time
O(n) per getMin
Space
O(n)
// getMin loops through internal array — fails O(1) requirement

Tradeoff:

2. Parallel min stack

Keep a second stack holding the running minimum at each level. Push the new min (or current min) on every push so pop stays aligned.

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

Tradeoff:

Flipkart-specific tips

Flipkart panels reward the explicit space-vs-time framing — they apply the same parallel-structure trick when keeping the lowest live price across product variants.

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

Practice these live with InterviewChamp.AI →