Min Stack

Try It Yourself

Use the editor below to process stack operations while supporting getMin in constant time. Track minimum history as values are pushed and popped.

Submit your implementation when it passes the examples. Duplicate minimum values must remain valid after one copy is removed.

Min Stack

mediumStack · Design30 minLC 155

Problem

Process a sequence of MinStack operations. push, pop, top, and getMin must all run in constant time.

Return one output per operation. Constructors, push, and pop produce null; top and getMin produce numbers.

Example 1:

Input: operations = ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"], values = [[], [-2], [0], [-3], [], [], [], []]

Output: [null, null, null, null, -3, null, 0, -2]

Example 2:

Input: operations = ["MinStack", "push", "getMin", "top"], values = [[], [5], [], []]

Output: [null, null, 5, 5]

Constraints

At most 30,000 operations are performed.
pop, top, and getMin are called only on a non-empty stack.

0 attempts

Solution

Keep a normal value stack and a second stack of minimums. Push onto the minimum stack whenever the new value is less than or equal to its current top.

When popping a value equal to the current minimum, pop the minimum stack too. Its new top then restores the previous minimum.

function runMinStack(operations, values) {
  class MinStack {
    constructor() {
      this.items = [];
      this.minimums = [];
    }

    push(value) {
      this.items.push(value);
      const minimum = this.minimums[this.minimums.length - 1];

      if (this.minimums.length === 0 || value <= minimum) {
        this.minimums.push(value);
      }
    }

    pop() {
      const value = this.items.pop();
      if (value === this.minimums[this.minimums.length - 1]) {
        this.minimums.pop();
      }
    }

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

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

  let stack;
  const output = [];

  for (let index = 0; index < operations.length; index++) {
    const operation = operations[index];

    if (operation === "MinStack") {
      stack = new MinStack();
      output.push(null);
    } else if (operation === "push") {
      stack.push(values[index][0]);
      output.push(null);
    } else if (operation === "pop") {
      stack.pop();
      output.push(null);
    } else if (operation === "top") {
      output.push(stack.top());
    } else {
      output.push(stack.getMin());
    }
  }

  return output;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	The wrapper processes n operations, and every stack operation is O(1).
Auxiliary space	`O(n)`	The value and minimum stacks can each hold up to n values.