Skip to main content

20. Min Stack

mediumAsked at Coinbase

Track the minimum portfolio value at O(1) cost — Coinbase asks this to test whether you can maintain auxiliary state for instant low-watermark reads without rescanning the full price history.

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

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 must run in O(1).

Constraints

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

Examples

Example 1

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

Explanation: getMin after push(-3) returns -3; after pop(), top is 0 and min reverts to -2.

Approaches

1. Two stacks (auxiliary min stack)

Maintain a parallel stack that records the running minimum at each push level. getMin peeks the auxiliary stack.

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

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

  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 (encode delta)

Store the difference between the value and the current min in the stack. Reconstruct min on pop without a second array.

Time
O(1) all ops
Space
O(n) (one array)
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 diff = this.stack.pop();
    if (diff < 0) this.min = this.min - diff;
  }

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

  getMin() {
    return this.min;
  }
}

Tradeoff:

Coinbase-specific tips

Coinbase likes the dual-stack approach in interviews because it is easy to reason about under pressure — but they often follow up asking whether you can reduce memory by encoding deltas. The delta trick shows you understand that auxiliary state does not always require a second full-size structure, which maps to how Coinbase thinks about memory efficiency in hot-path market data pipelines.

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

Practice these live with InterviewChamp.AI →