006 — Min Stack¶

Source¶

Original source: Classic design exercise
Platform: LeetCode — https://leetcode.com/problems/min-stack/
Topic: stack, design
Difficulty: Easy
Pattern: design composition (twin stack)
Basic idea inherited from: "maintain the needed history" tweak — যে তথ্য O(1)-তে চাই, সেটাকে lockstep-এ একটা twin structure-এ রাখো

1. Problem in simple words¶

একটা সাধারণ stack বানাও, কিন্তু তার সাথে একটা বাড়তি ক্ষমতা — যেকোনো মুহূর্তে stack-এর সবচেয়ে ছোট element O(1)-তে বলতে পারা। চারটা method:

push(val) — উপরে একটা element রাখো।
pop() — উপরের element সরাও।
top() — উপরের element দেখো।
get_min() — পুরো stack-এর minimum দেখো, O(1)-তে।

2. Which basic idea does this inherit from?¶

এটা "maintain the needed history" tweak-এর সরাসরি প্রয়োগ (../patterns.md-এর Pattern 3): যখন কোনো query স্বাভাবিকভাবে ধীর মনে হয়, জিজ্ঞেস করো "এর instant উত্তর দিতে কোন history-টা লাগত?" — তারপর সেই history-টা একটা দ্বিতীয় structure-এ, মূল structure-এর সাথে lockstep-এ, রেখে দাও।

3. What is the hidden math or logic?¶

লুকানো logic হলো prefix-minimum-এর monotone behaviour: একটা stack যেহেতু শুধু শেষ প্রান্তে বাড়ে-কমে, তাই "এই depth পর্যন্ত minimum কত" — এই তথ্যটাও stack-এর মতোই push/pop হয়। তাই প্রতিটা element-এর পাশে "এই element সহ এখন পর্যন্ত minimum" রেকর্ড করে রাখলে, top-এর সেই রেকর্ডই পুরো stack-এর minimum।

invariant: mins[i] = মূল stack-এর শুরু থেকে index i পর্যন্ত সব element-এর minimum। তাই mins[-1] সবসময় পুরো stack-এর min।

4. Which data structure is needed?¶

দুটো stack — একটা main stack (আসল value), আর একটা twin mins stack, যেখানে প্রতিটা position-এ "ওই position পর্যন্ত running minimum" রাখা।

5. Why this data structure fits¶

minimum বের করতে পুরো stack scan করলে O(n) লাগত। কিন্তু stack যেহেতু শুধু top-এ বদলায়, running minimum-ও top-এর সাথেই push/pop হয় — তাই একটা twin stack-এ সেটা সংরক্ষণ করলে get_min নেমে আসে O(1)-তে। প্রতিটা operation (push/pop/top/get_min) তখন O(1), যা ছাড়া get_min ধীর হতো।

6. Real-life analogy¶

পাহাড়ে চড়ার সময় প্রতিটা ক্যাম্পে একটা note রেখে যাওয়া ভাবো: "এই ক্যাম্প পর্যন্ত সবচেয়ে নিচু উচ্চতা যেটা পেরিয়ে এসেছি।" নতুন ক্যাম্পে পৌঁছে আগের note আর এখনকার উচ্চতার মধ্যে যেটা ছোট, সেটা নতুন note। নিচে নামার সময় (pop) note-ও তুলে নাও। যেকোনো ক্যাম্পে দাঁড়িয়ে শেষ note-টা পড়লেই এ পর্যন্ত minimum জানা — খুঁজতে যেতে হয় না।

7. Visual explanation¶

push(-2), push(0), push(-3), তারপর get_min, pop, get_min:

op          stack            mins (running min)      get_min
push(-2)    [-2]             [-2]
push(0)     [-2, 0]          [-2, -2]   (min(0,-2)=-2)
push(-3)    [-2, 0, -3]      [-2, -2, -3]  (min(-3,-2)=-3)
get_min     ->                                       mins[-1] = -3
pop         [-2, 0]          [-2, -2]    (দুটোই pop)
get_min     ->                                       mins[-1] = -2

দুটো stack সবসময় একসাথে push/pop হয় — তাই top দুটো সবসময় সারিবদ্ধ।

8. Example input and output¶

ops    : push(-2), push(0), push(-3), get_min(), pop(), top(), get_min()
out    :    -         -         -        -3        -3     0       -2

Edge case (একটাই element): push(5), get_min() -> 5; pop(); push(5),push(5),pop(),get_min() -> 5 (duplicate min)

9. Brute force thinking¶

সহজ চিন্তা: শুধু একটা সাধারণ stack রাখি; get_min চাইলে পুরো stack scan করে minimum বের করি।

get_min(): min(stack)   # পুরো stack ঘুরে দেখো

10. Why brute force is slow¶

ওই min(stack) প্রতিবার O(n)। যদি বহুবার get_min ডাকা হয় (যা এই design-এর মূল উদ্দেশ্য), তাহলে এটা ব্যয়বহুল। চ্যালেঞ্জটাই হলো get_min-কে O(1) করা — আর সেটা twin stack ছাড়া হয় না।

11. Key observation¶

মূল observation: stack শুধু top-এ বদলায়, তাই "এখন পর্যন্ত minimum"-ও top-এর সাথে সাথেই বদলায়। একটা element pop হলে minimum হয় আগের অবস্থায় ফিরে যায় — তাই প্রতিটা depth-এর জন্য minimum আলাদা করে মনে রাখা সম্ভব, এবং তা stack-এর মতোই আচরণ করে।

12. Optimized intuition¶

দুটো stack রাখো। push(val): stack-এ val রাখো; mins-এ রাখো min(val, mins-এর বর্তমান top) (mins খালি হলে শুধু val)। pop: দুটো stack থেকেই pop করো। top: stack[-1]। get_min: mins[-1] — O(1)।

13. Thinking tweak¶

মোচড়: "minimum তো খুঁজে বের করতে হয়" — এই ধারণাটা বদলে দাও। minimum-কে খুঁজো না, বরং প্রতিটা push-এর সময় আগেভাগেই হিসাব করে রেখে দাও। সামান্য বাড়তি জায়গার বিনিময়ে query হয়ে যায় instant।

14. Step-by-step dry run¶

operations: push(-2), push(0), push(-3), get_min(), pop(), top(), get_min():

push(-2) → stack=[-2], mins=[-2]
push(0) → stack=[-2, 0], mins=[-2, min(0,-2)=-2] = [-2, -2]
push(-3) → stack=[-2, 0, -3], mins=[-2, -2, min(-3,-2)=-3] = [-2, -2, -3]
get_min() → mins[-1] = -3
pop() → দুটোই pop → stack=[-2, 0], mins=[-2, -2]
top() → stack[-1] = 0
get_min() → mins[-1] = -2

15. Python solution¶

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []                      # twin: প্রতি depth-এ running min

    def push(self, val):
        self.stack.append(val)
        if not self.mins:
            self.mins.append(val)
        else:
            self.mins.append(min(val, self.mins[-1]))

    def pop(self):
        self.mins.pop()                     # দুটো একসাথে pop
        return self.stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.mins[-1]                # O(1)!

# ---- tests ----
ms = MinStack()
ms.push(-2)
ms.push(0)
ms.push(-3)
assert ms.get_min() == -3
assert ms.pop() == -3
assert ms.top() == 0
assert ms.get_min() == -2

# duplicate minimum ঠিকভাবে সামলায় কিনা
ms2 = MinStack()
ms2.push(5)
ms2.push(5)
assert ms2.get_min() == 5
ms2.pop()
assert ms2.get_min() == 5          # এখনো একটা 5 আছে
print("সব test pass!")

16. Line-by-line code explanation¶

self.stack, self.mins — মূল value আর running-min, দুটো সমান্তরাল stack।
push(val): stack-এ value; mins খালি হলে val, নাহলে min(val, mins[-1]) — মানে "নতুন value আর এতক্ষণের min-এর মধ্যে ছোটটা"।
pop(): দুটো stack থেকেই pop, যাতে সারিবদ্ধতা বজায় থাকে; মূল value return করে।
top(): stack[-1]।
get_min(): mins[-1] — সবসময় পুরো stack-এর minimum, O(1)।

17. Output walkthrough¶

push(-2/0/-3)-এর পর mins = [-2, -2, -3], তাই get_min() = -3। pop() দুটো stack থেকেই top সরায় → mins = [-2, -2]। top() = 0, get_min() = -2। duplicate-min test-এ দুটো 5 push করে একটা pop করলেও get_min() এখনো 5। সব assert pass — print: সব test pass!।

18. Time complexity¶

প্রতিটা operation (push, pop, top, get_min) O(1) — কোনো scan নেই, সবই top-এ কাজ।

19. Space complexity¶

O(n) — মূল stack-এর পাশাপাশি সমান আকারের mins stack রাখতে হয় (n element-এর জন্য 2n storage)।

20. Common mistakes¶

push-এ min না নিয়ে শুধু val রাখা — তাহলে mins running minimum হয় না, get_min ভুল দেয়।
duplicate minimum ভুলভাবে সামলানো — min(val, mins[-1]) ব্যবহারে দুটো সমান min থাকলে দুটো entry-ই min ধরে রাখে, তাই একটা pop করলেও min ঠিক থাকে। (একটা single-value "min variable" রাখলে এই কেসে ভুল হতো।)
pop-এ শুধু এক stack থেকে pop করা — দুটো stack-এর সারিবদ্ধতা ভেঙে যায়।

21. Which basic problem this inherits from¶

ভিত্তি: stack-এর push/pop discipline + "maintain the needed history" design tweak; chapter-এর ../patterns.md-এর Pattern 3 (Design Compositions) আর ../concept.md-এর core invariant তালিকা। এটা problem 4/5-এর design-composition পরিবারেরই সদস্য।

22. Similar harder problems¶

Max Stack (min-এর বদলে max, সাথে popMax) — https://leetcode.com/problems/max-stack/
Sliding Window Maximum (running max, monotonic deque দিয়ে) — https://leetcode.com/problems/sliding-window-maximum/ (এই tracker-এর #19)
Implement Queue using Stacks — https://leetcode.com/problems/implement-queue-using-stacks/ (#4)

23. Pattern learned¶

Twin stack for O(1) aggregate: মূল structure-এর পাশে একটা সমান্তরাল stack-এ "এখন পর্যন্ত min/max/aggregate" lockstep-এ রাখো — query হয়ে যায় O(1)।

24. Final summary¶

ভবিষ্যতের আমাকে: "O(1)-তে min/max চাই? — push-এর সময় running value আগেভাগে twin stack-এ রেখে দাও।" "design a structure that supports X in O(1)" দেখলেই জিজ্ঞেস করবে: কোন history lockstep-এ maintain করলে query সস্তা হয়।

25. JavaScript solution (with test cases)¶

twin stack — main value আর running-min lockstep-এ push/pop, তাই getMin O(1)।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// stack with O(1) getMin (twin stack)
class MinStack {
  constructor() {
    this.stack = [];
    this.mins = [];                    // twin: প্রতি depth-এ running min
  }
  push(val) {
    this.stack.push(val);
    if (this.mins.length === 0) this.mins.push(val);
    else this.mins.push(Math.min(val, this.mins[this.mins.length - 1]));
  }
  pop() {
    this.mins.pop();                   // দুটো একসাথে pop
    return this.stack.pop();
  }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }  // O(1)!
}
// ---- test cases (example + edge) ----
const ms = new MinStack();
ms.push(-2); ms.push(0); ms.push(-3);
assert(ms.getMin() === -3, "min-after-push");
assert(ms.pop() === -3, "pop-returns-top");
assert(ms.top() === 0, "top");
assert(ms.getMin() === -2, "min-after-pop");
// duplicate minimum ঠিকভাবে সামলায় কিনা (edge)
const ms2 = new MinStack();
ms2.push(5); ms2.push(5);
assert(ms2.getMin() === 5, "dup-min");
ms2.pop();
assert(ms2.getMin() === 5, "dup-min-still");
console.log("সব JS test pass!");

JS টীকা: stack হিসেবে array; top দেখতে arr[arr.length - 1] (Python-এর arr[-1]-এর সমতুল্য, কারণ JS-এ negative index কাজ করে না)। প্রতিটা depth-এ Math.min(val, prevMin) রাখায় duplicate min-ও সঠিকভাবে সামলায়।

26. TypeScript solution (with test cases)¶

class MinStack {
  private stack: number[] = [];
  private mins: number[] = [];          // running min per depth
  push(val: number): void {
    this.stack.push(val);
    if (this.mins.length === 0) this.mins.push(val);
    else this.mins.push(Math.min(val, this.mins[this.mins.length - 1]));
  }
  pop(): number | undefined {
    this.mins.pop();
    return this.stack.pop();
  }
  top(): number { return this.stack[this.stack.length - 1]; }
  getMin(): number { return this.mins[this.mins.length - 1]; }
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const ms = new MinStack();
ms.push(-2); ms.push(0); ms.push(-3);
expect(ms.getMin(), -3, "min-after-push");
expect(ms.pop(), -3, "pop-returns-top");
expect(ms.top(), 0, "top");
expect(ms.getMin(), -2, "min-after-pop");
console.log("সব TS test pass!");

TS টীকা: private stack/mins দিয়ে দুই internal stack-কে বাইরে থেকে আলাদাভাবে বদলানো আটকানো হয় (lockstep invariant রক্ষা); method-এর typed signature ভুল ব্যবহার compile-time-এ ধরে।

27. কোথায় কাজে লাগে (real-world use)¶

Running min/max tracking: undo-able stack-এ যেকোনো মুহূর্তে সর্বনিম্ন/সর্বোচ্চ O(1)-এ চাই এমন যেকোনো জায়গা।
Stock/price monitoring: push/pop হওয়া window-তে চলমান সর্বনিম্ন দাম instant জানা।
Browser/editor history: state stack-এর পাশে aggregate (min cost, max depth) lockstep রাখা।
Expression evaluation: operand stack-এর পাশে running statistic ধরে রাখা।
Resource monitors: allocate/free stack-এ সর্বনিম্ন available level track করা।
Game state: move stack-এর পাশে best/worst score O(1)-এ ধরে রাখা।

মূল pattern: query ধীর মনে হলে জিজ্ঞেস করো "কোন history lockstep-এ রাখলে এটা O(1) হয়" — তারপর সেই history twin structure-এ আগেভাগে রেখে দাও।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।