4.3 Design Problems (Custom Stack/Queue)

Demo: Min Stack — LC 155 (Medium — Amazon/Google High)

Statement (Demo): Design MinStack with push(val), pop(), top() and getMin(), all O(1). getMin() always returns the current minimum. Example: push(-2), push(0), push(-3) → getMin()=-3, pop(), top()=0, getMin()=-2 | ⚡ at most 3×10⁴ calls

Approach: Store each element paired with "the minimum so far" — popping automatically restores the previous minimum.

class MinStack {
  constructor() {
    this.stack = [];
  } // [value, minSoFar] pairs
  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];
  }
}

Complexity: Every operation O(1), Space O(n)