Skip to main content

7. Min Stack

easyAsked at JetBrains

Design a stack supporting push/pop/top/getMin all in O(1) — JetBrains uses this to gauge whether you can maintain auxiliary invariants in scope-stack data structures.

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

Problem

Implement a MinStack class with push, pop, top, and getMin all running in constant time. getMin must reflect the current minimum after any push or pop.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • <= 3 * 10^4 operations total
  • pop, top, getMin only on non-empty stacks

Examples

Example 1

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

Example 2

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

Approaches

1. Scan-on-getMin

Push and pop on a single stack; recompute min by scanning on each getMin call.

Time
O(n) per getMin
Space
O(n)
class MinStack { constructor(){this.s=[]}
 push(v){this.s.push(v)} pop(){this.s.pop()} top(){return this.s.at(-1)}
 getMin(){return Math.min(...this.s)} }

Tradeoff:

2. Auxiliary running-min stack

Keep a parallel stack that records the running min at every push. Pop both stacks together. Same auxiliary-state pattern JetBrains scope analyzers use.

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

Tradeoff:

JetBrains-specific tips

JetBrains expects you to call out the auxiliary-invariant pattern — scope analyzers maintain parallel state stacks for type bounds, nullability, and visibility in O(1) per token.

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

Practice these live with InterviewChamp.AI →