7. Min Stack

Design a stack that supports push, pop, top and retrieving the minimum element, all in O(1) time.

Implement the MinStack class:

MinStack() creates an empty stack.
push(val) pushes val.
pop() removes the top element.
top() returns the top element.
getMin() returns the smallest element in the stack.

Tests call the methods in sequence; pop, top and getMin are only called on a non-empty stack.

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 minimum is -3. Popping -3 leaves 0 on top and -2 as the minimum.

Constraints

-2^31 <= val <= 2^31 - 1
At most 3 * 10^4 calls in total

💡 Hint 1

The minimum can change when you pop. Can you remember what the minimum was at every depth of the stack?

💡 Hint 2

Store pairs (value, minimum so far), or keep a second stack of minimums.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Keep a single stack of pairs: each entry stores the value and the minimum of the stack at the moment it was pushed (min(val, previousMin)). top reads the value, getMin reads the stored minimum, and popping automatically restores the previous minimum.

Time O(1) per operationSpace O(n)

class MinStack {
  constructor() {
    this.stack = [];
  }
  push(val) {
    const min = this.stack.length ? Math.min(val, this.getMin()) : val;
    this.stack.push([val, min]);
  }
  pop() {
    this.stack.pop();
  }
  top() {
    return this.stack[this.stack.length - 1][0];
  }
  getMin() {
    return this.stack[this.stack.length - 1][1];
  }
}

class MinStack {
    private final Deque<int[]> stack = new ArrayDeque<>();

    public MinStack() {}

    public void push(int val) {
        int min = stack.isEmpty() ? val : Math.min(val, stack.peek()[1]);
        stack.push(new int[] { val, min });
    }

    public void pop() { stack.pop(); }

    public int top() { return stack.peek()[0]; }

    public int getMin() { return stack.peek()[1]; }
}

class MinStack {
  constructor() {

  }

  /** @param {number} val */
  push(val) {

  }

  pop() {

  }

  /** @return {number} */
  top() {

  }

  /** @return {number} */
  getMin() {

  }
}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit