Skip to main content

21. Min Stack

easyAsked at Datadog

Design a stack that supports push, pop, top, and getMin all in O(1). Datadog asks this because it's the same shape as a streaming min-aggregate that needs to handle rollbacks (transactional ingestion).

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite design-warmup — graded on the parallel-stack insight.
  • Blind (2025-11)— Recurring at Datadog onsites.

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() — all O(1).

Constraints

  • -2^31 <= val <= 2^31 - 1
  • Methods pop, top and getMin operations will always be called on non-empty stacks.
  • At most 3 * 10^4 calls will be made.

Examples

Example 1

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

Approaches

1. Recompute min on every getMin

Single stack; scan on every getMin call.

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

Tradeoff: getMin is O(n). Datadog will fail this for missing the constant-time requirement.

2. Parallel min stack (optimal)

Maintain a second stack of running minima. On push, push min(val, currentMin). On pop, pop both.

Time
O(1) all ops
Space
O(n)
class MinStack {
  constructor() {
    this.s = [];
    this.mins = [];
  }
  push(v) {
    this.s.push(v);
    if (this.mins.length === 0 || v <= this.mins[this.mins.length - 1]) {
      this.mins.push(v);
    } else {
      this.mins.push(this.mins[this.mins.length - 1]);
    }
  }
  pop() {
    this.s.pop();
    this.mins.pop();
  }
  top() { return this.s[this.s.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

Tradeoff: All ops O(1). The parallel-stack pattern is exactly what Datadog uses for rollback-able running aggregates.

Datadog-specific tips

Datadog cares whether you can articulate the invariant: 'mins[i] = the minimum of stack[0..i].' Variants they ask: 'reduce memory by only pushing onto mins when val <= current min' — works, but pop logic gets trickier (only pop mins when val === current min).

Common mistakes

  • Using Math.min(...this.s) — looks like O(1) but is O(n) per call. Hidden bug.
  • Only pushing onto mins when val < currentMin (strict) — breaks on equal values during pop.
  • Forgetting to push to BOTH stacks symmetrically — desyncs and corrupts state.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Min Queue — same idea but FIFO; needs two deques.
  • Max Stack (LC 716) — symmetric problem.
  • Datadog-style: rollback-able streaming min over a transactional ingest log.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Can you save memory by not pushing every time?

Yes — only push to mins when val <= current min. But then pop logic must check whether the val being popped equals the top of mins, and pop mins only when so.

Why two stacks instead of one with pairs?

Equivalent memory; two stacks are cleaner because pop on each is independent and you avoid object allocation per push.

Practice these live with InterviewChamp.AI

Drill Min Stack and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →