Min Stack

Examples

Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: getMin() -> -3, then after pop() the stack holds -2, 0; top() -> 0, getMin() -> -2

After the three pushes, the stack holds -2, 0, -3 (bottom to top), so the minimum is -3. Popping removes -3; now the top is 0, and the smallest of what remains (-2 and 0) is -2.

Input: push(1), push(2), getMin(), pop(), getMin()
Output: getMin() -> 1, then after pop() removes 2, getMin() -> 1

1 stays the minimum throughout, since 2 gets popped off without ever having been the smallest.

Constraints

• pop, top, and getMin are only ever called when the stack is non-empty.

• At most 3 * 10^4 calls total will be made to push/pop/top/getMin.

Approach

The tricky part isn't tracking the minimum while pushing — that's easy, just compare against a running minimum. The hard part is popping: if you pop the element that happens to be the current minimum, you need to know what the minimum was before that element was pushed, and a single variable can't tell you that.

The fix is to keep a second, parallel stack — call it the min-stack — where each entry records "what was the minimum value in the stack at the moment this element was pushed". Every push adds one entry to both stacks, and every pop removes one entry from both. That way, the top of the min-stack is always the correct current minimum, automatically kept in sync with whatever's actually left in the main stack.

Solutions

Brute Force — Scan for the Minimum

Keep a single plain array as the stack. push, pop, and top are trivial O(1) array operations, but getMin() has to scan the entire stack every single time it's called.

class MinStack {
  constructor() {
    this.stack = [];
  }

  push(val) {
    this.stack.push(val);
  }

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

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

  getMin() {
    return Math.min(...this.stack);
  }
}

Time: push/pop/top: O(1), getMin: O(n) · Space: O(n)

Optimal — Auxiliary Min Stack

Maintain a second stack alongside the main one, where each entry is 'the minimum value in the stack right after this push'. Popping either stack always leaves the correct minimum on top of the min-stack.

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];
  }
}

Time: O(1) for push, pop, top, and getMin · Space: O(n), for the extra min-tracking stack