Skip to main content

23. Min Stack

mediumAsked at Asana

Design a stack that retrieves the minimum element in O(1) — Asana applies this auxiliary-stack pattern when tracking the minimum-priority task visible in a collapsible project section without rescanning the full list.

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() — returns the top element, and getMin() — returns the minimum element.

Constraints

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

Examples

Example 1

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

Explanation: After pushing -2, 0, -3: min is -3. After pop(-3): top is 0, min is -2.

Approaches

1. Auxiliary min-stack

Maintain a parallel stack of minimums. On push, record min(current, minStack.top). On pop, also pop the min stack. getMin is O(1).

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

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

  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 (space-optimized)

Store (val - currentMin) on the stack. When the delta is negative a new minimum was set. Reconstruct on pop. Uses one stack but encodes state in the values.

Time
O(1) all ops
Space
O(n) single stack
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 top = this.stack.pop();
    if (top < 0) this.min = this.min - top; // restore previous min
  }

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

  getMin() {
    return this.min;
  }
}

Tradeoff:

Asana-specific tips

Asana expects you to reach for the two-stack approach first — it's clean, obviously correct, and easy to maintain. The delta-encoding variant is a talking point to show depth, not the expected primary solution. Name the insight explicitly: 'Every element needs to remember the minimum at the time it was pushed, so I pair the main stack with a parallel min-stack.' Class-based design with clear method contracts mirrors real Asana API design thinking.

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

Practice these live with InterviewChamp.AI →