Skip to main content

20. Min Stack

mediumAsked at Databricks

Design a stack that retrieves its minimum in O(1) — Databricks uses this to test auxiliary-state discipline, a pattern that shows up when tracking minimum-cost DAG nodes in a query optimizer.

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

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. Implement the MinStack class: - MinStack() initializes the stack - push(val) pushes val onto the stack - pop() removes the top element - top() returns the top element - getMin() retrieves the minimum element

Constraints

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

Examples

Example 1

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

Explanation: After pushing -2, 0, -3 the min is -3. After popping -3, top is 0 and min reverts to -2.

Approaches

1. Two stacks

Maintain a main stack and a parallel min-stack. Each push records the current minimum at that depth; pop removes from both.

Time
O(1) all ops
Space
O(n)
class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }

  push(val) {
    this.stack.push(val);
    const min = this.minStack.length === 0
      ? val
      : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(min);
  }

  pop() {
    this.stack.pop();
    this.minStack.pop();
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  getMin() {
    return this.minStack[this.minStack.length - 1];
  }
}

Tradeoff:

2. Single stack with encoded delta

Store the difference (val - currentMin) in the stack instead of val. When popping a negative delta, the previous min can be recovered. Halves the stack's object-count but adds encoding complexity.

Time
O(1) all ops
Space
O(n)
class MinStack {
  constructor() {
    this.stack = [];
    this.min = Infinity;
  }

  push(val) {
    if (this.stack.length === 0) {
      this.stack.push(0);
      this.min = val;
    } else {
      this.stack.push(val - this.min);
      if (val < this.min) this.min = val;
    }
  }

  pop() {
    const delta = this.stack.pop();
    if (delta < 0) this.min = this.min - delta;
  }

  top() {
    const delta = this.stack[this.stack.length - 1];
    return delta < 0 ? this.min : this.min + delta;
  }

  getMin() {
    return this.min;
  }
}

Tradeoff:

Databricks-specific tips

Databricks system-design rounds often explore variations of this pattern at scale: how do you track running minima across thousands of concurrent Spark tasks without centralizing state? Lead with the two-stack approach (clearer invariant), then mention the delta-encoding variant to show depth — that jump signals senior-level systems thinking to the interviewer.

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

Practice these live with InterviewChamp.AI →