4.3 Design Problems (Custom Stack/Queue)

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

Statement (Demo): MinStack class design করুন — push(val), pop(), top(), getMin() সবগুলো O(1) time-এ কাজ করবে। getMin() সবসময় বর্তমান stack-এর minimum value return করবে। উদাহরণ: push(-2), push(0), push(-3) → getMin()=-3, pop(), top()=0, getMin()=-2 | ⚡ max 3×10⁴ calls

Approach: প্রতিটা এলিমেন্টের সাথে "এই পর্যন্ত min" জোড়া করে রাখুন — pop করলে min-ও আপনা-আপনি আগের অবস্থায় ফিরে যায়।

class MinStack {
  constructor() {
    this.stack = [];
  } // [value, minSoFar] জোড়া
  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: সব operation O(1), Space O(n)