# Stack and Queue — Problem-Solving Patterns পাঁচটা pattern। প্রথম দুটো ডাল-ভাত; শেষ তিনটায় (monotonic stack, monotonic deque) stack আর queue হয়ে ওঠে *thinking tool*, যেগুলো O(n^2) scan-কে O(n) sweep-এ নামিয়ে আনে। Pattern 5, Sliding Window Maximum, এই chapter-এর required centerpiece — নিজে re-derive করতে না পারা পর্যন্ত study করো। --- ## Pattern 1 — Matching / Nesting / Undo (the stack) **Trigger words:** "valid parentheses", "balanced", "nested", "decode", "simplify path", "undo", "backspace", "most recent"। **Core idea:** stack ধরে রাখে প্রতিটা *opened-but-unfinished* context। একটা closing event-কে অবশ্যই **top**-এর সাথে মিলতে হবে (সবচেয়ে recently খোলা context); শেষ হলে সেটা pop হয়, নিচের context-টা বেরিয়ে আসে। **The thinking tweak:** "string-টা scan করে pair খুঁজি" — এভাবে ভেবো না। ভাবো "প্রতি মুহূর্তে, আমি *কীসের ভেতরে* আছি?" — stack-টাই হলো exact উত্তর, innermost-টা উপরে। **Worked example — `"([)]"` কি valid?** ```text '(' open -> stack: ( '[' open -> stack: ( [ ')' close -> top is '[' but ')' needs '(' -> MISMATCH -> invalid The brackets interleave instead of nesting; the stack catches it instantly. Three failure modes to handle: pop-on-empty, mismatch, leftovers at end. ``` **Inherits from:** raw push/pop। এটা stack-এর discipline সরাসরি ব্যবহার করা, কোনো twist ছাড়া। **Representative problems:** - Valid parentheses — [LeetCode 20](https://leetcode.com/problems/valid-parentheses/) — [Valid Parentheses: বাংলা নোট](problems/001-valid-parentheses.md) - Nested string `3[a2[c]]` decode করো — [LeetCode 394](https://leetcode.com/problems/decode-string/) — [Decode String: বাংলা নোট](problems/010-decode-string.md) - Backspace string compare — [LeetCode 844](https://leetcode.com/problems/backspace-string-compare/) — [Backspace String Compare: বাংলা নোট](problems/003-backspace-compare.md) ## Pattern 2 — BFS Frontier (the queue) **Trigger words:** "shortest number of steps/moves", "minimum operations to reach", "level order", "spreads each minute", "nearest"। **Core idea:** Ring-এ ring-এ বাইরের দিকে explore করো। Queue ধরে রাখে frontier; FIFO reorder করতে পারে না বলে, সব distance-d node dequeue হয় যেকোনো distance-(d+1) node-এর আগে — তাই কোনো node-এ প্রথমবার পৌঁছানো মানেই সেটা একটা shortest path দিয়ে। **The thinking tweak:** queue শুধু storage না — তার *ordering guarantee-টাই হলো correctness-এর proof*। এটা stack দিয়ে বদলে দাও আর তুমি পাবে DFS, যেটা *একটা* path পায়, shortest-টা না। **Worked example — grid-এ S থেকে T-তে minimum step:** সমান cost-এর edge ধরে নিচের ছোট graph: ```text S -> A -> T S -> B শুরু: queue=[S(0)] pop S: queue=[A(1),B(1)] pop A: queue=[B(1),T(2)] pop B: queue=[T(2)] pop T: distance=2, শেষ ``` Visited চিহ্ন enqueue করার সময় দাও। Weighted graph-এ এই shortest-distance যুক্তি সরাসরি প্রযোজ্য নয়। **Inherits from:** সাধারণ queue discipline। Full treatment (graphs, multi-source BFS, 0-1 BFS) থাকে [../09-graphs/](../09-graphs/README.md)-এ — এই chapter শুধু তাকে সঠিক container-টা ধরিয়ে দেয়। **Representative problems:** - Connected region count করো (BFS flood fill) — [LeetCode 200](https://leetcode.com/problems/number-of-islands/) — [Number of Islands: বাংলা নোট](problems/012-number-of-islands.md) - ছড়াতে থাকা process, শেষ হতে কত মিনিট — [LeetCode 994](https://leetcode.com/problems/rotting-oranges/) — [Rotting Oranges: বাংলা নোট](problems/013-rotting-oranges.md) - Binary tree-র level-order traversal — [LeetCode 102](https://leetcode.com/problems/binary-tree-level-order-traversal/) — [Binary Tree Level Order Traversal: বাংলা নোট](problems/014-level-order-traversal.md) ## Pattern 3 — Design Compositions (two stacks, twin stacks) **Trigger words:** "implement a queue using stacks", "O(1) get_min", "design a stack that..."। **Core idea:** restricted structure গুলো combine করে এমন একটা capability বানাও যেটা তাদের আলাদাভাবে নেই। দুটো reversal মিলে একটা forward order: একটা `in` stack-এ push করো; `out` খালি হলে, `in`-টা `out`-এ ঢেলে দাও (reverse হয়ে যায়); `out` থেকে pop করো — দুটো LIFO থেকে FIFO, amortized O(1)। MinStack: একটা twin stack প্রতিটা depth-এ running minimum record করে রাখে (দেখো [operations.md](operations.md) section 10)। **The thinking tweak:** কোনো operation যখন একটা structure-এর নিয়মে অসম্ভব মনে হয়, জিজ্ঞেস করো "এটার instant উত্তর দিতে আমার কোন *history*-টা লাগত?" — তারপর সেই history-টা একটা দ্বিতীয় structure-এ maintain করো, lockstep-এ update করে। **Worked example — দুটো stack থেকে queue, operations `enq 1, enq 2, deq, enq 3, deq`:** ```text enq 1: in=[1] out=[] enq 2: in=[1,2] out=[] deq : out empty -> pour: out=[2,1]; pop out -> 1 (correct FIFO!) enq 3: in=[3] out=[2] deq : out not empty -> pop out -> 2 (still FIFO) each element is moved at most twice ever -> amortized O(1) ``` **Inherits from:** dynamic array-র amortized argument ([../02-arrays-and-strings/](../02-arrays-and-strings/README.md)) — কালেভদ্রে একটা বড় cost দাও, সেটা অনেকগুলো সস্তা operation-এর ঘাড়ে চাপাও। **Representative problems:** - Stack দিয়ে queue — [LeetCode 232](https://leetcode.com/problems/implement-queue-using-stacks/) — [Implement Queue using Stacks: বাংলা নোট](problems/004-queue-via-stacks.md) - Queue দিয়ে stack — [LeetCode 225](https://leetcode.com/problems/implement-stack-using-queues/) — [Implement Stack using Queues: বাংলা নোট](problems/005-stack-via-queues.md) - Min stack — [LeetCode 155](https://leetcode.com/problems/min-stack/) — [Min Stack: বাংলা নোট](problems/006-min-stack.md) ## Pattern 4 — Monotonic Stack (next/previous greater or smaller) **Trigger words:** "next greater element", "previous smaller", "days until a warmer day", "stock span", "largest rectangle", "can see / is blocked by"। **Core idea:** একবার scan করো, এমন index-দের একটা stack রেখে যাদের answer এখনো unknown, তাদের value গুলো monotonic রাখা (যেমন decreasing)। প্রতিটা নতুন element pop করে — আর সেভাবেই *answer দিয়ে দেয়* — stack-এ থাকা প্রত্যেককে যাদের সে হারায়, তারপর নিজে stack-এ যোগ দেয়। **The thinking tweak:** প্রশ্নটা উল্টে দাও। প্রতিটা element নিজের answer-এর জন্য *সামনে search করার* বদলে (O(n^2)), প্রতিটা নতুন element-কে দিয়ে answer পেছনে *deliver* করাও — যাদের সে dominate করে তাদের সবাইকে। প্রতিটা element একবার push হয় আর বড়জোর একবার pop হয় → O(n) total, nested-দেখতে loop সত্ত্বেও। **Worked example — `[2, 1, 5, 3]`-এর next greater:** ```text 2 arrives: nobody waiting -> wait. stack(vals): [2] 1 arrives: beats nobody -> wait. stack: [2, 1] 5 arrives: beats 1 -> ans(1)=5; beats 2 -> ans(2)=5; wait. stack: [5] 3 arrives: beats nobody -> wait. stack: [5, 3] end: 5 and 3 never beaten -> -1. answers: [5, 5, -1, -1] ``` **Inherits from:** Pattern 1-এর "most recent unfinished" discipline — এখানে "unfinished" মানে "answer এখনো পাওয়া যায়নি"। Counting flavor-টা (প্রতিটা element কয়টা subarray-র minimum?) সোজা ঢুকে যায় **contribution technique**-এ: দেখো sum-of-subarray-minimums [../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এ আর [LeetCode 907](https://leetcode.com/problems/sum-of-subarray-minimums/)। **Representative problems:** - কত দিন পর গরম temperature — [LeetCode 739](https://leetcode.com/problems/daily-temperatures/) — [Daily Temperatures: বাংলা নোট](problems/009-daily-temperatures.md) - Histogram-এর largest rectangle — [LeetCode 84](https://leetcode.com/problems/largest-rectangle-in-histogram/) — [Largest Rectangle in Histogram: বাংলা নোট](problems/020-largest-rectangle.md) - Sum of subarray minimums (monotonic stack + contribution) — [LeetCode 907](https://leetcode.com/problems/sum-of-subarray-minimums/) — [Sum of Subarray Minimums: বাংলা নোট](problems/017-sum-subarray-minimums.md) ## Pattern 5 — Monotonic Deque (REQUIRED worked example: Sliding Window Maximum) **Trigger words:** "maximum (or minimum) of every window of size k", "sliding window max/min", "best value within the last k items", windowed DP optimization। **Problem-টা (আমাদের নিজেদের ভাষায়):** একটা array আর একটা window size k দেওয়া আছে; বাঁ থেকে ডানে slide করতে করতে k element-এর প্রতিটা contiguous window-র maximum report করো। Official statement: [LeetCode 239 — Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)। **কী থেকে inherit করে:** [../02-arrays-and-strings/patterns.md](../02-arrays-and-strings/patterns.md)-এর **sliding window basic** (এক step করে এগোতে থাকা একটা window) **প্লাস the queue** — window-র candidate-রা এক প্রান্তে ঢোকে আর FIFO order-এ অন্য প্রান্তে expire করে। নতুন উপাদানটা হলো *পেছনের* প্রান্তকেও eject করতে দেওয়া — যেটা queue-টাকে upgrade করে একটা **deque**-এ। **Data structure:** `collections.deque`, যেটা রাখে **index** (index থাকলে আমরা ধরতে পারি front-টা কখন window থেকে বেরিয়ে গেছে)। **The thinking tweak — useless element গুলো window থেকে ফেলে দাও:** একটা নতুন value x এলে, deque-র যেকোনো element যেটা **x-এর চেয়ে ছোট, সেটা ভবিষ্যতের কোনো window-র জন্যই আর কখনো answer হতে পারবে না** — x একইসাথে নতুন (তাই তাদের চেয়ে বেশিদিন বাঁচবে) আর বড় (তাই তাদের চেয়ে এগিয়ে থাকবে)। x ঢোকার আগে এমন সব element পেছন থেকে eject করো। যা টিকে থাকে তা হলো এমন একটা deque যার value গুলো front থেকে back পর্যন্ত strictly কমে — **তাই front-টাই সবসময় current window-র max ধরে রাখে**। **Full algorithm-টা, প্রতিটা নতুন index i-এর জন্য:** ```text 1. while deque non-empty and value[back] <= value[i]: pop back (useless) 2. push i at the back 3. if front index <= i - k: pop front (expired) 4. if i >= k - 1: answer for this window = value[front] ``` **Worked example — `[1, 3, -1, -3, 5, 3, 6, 7]`, k = 3:** ```text i val deque after step (values) window max (front) 0 1 [1] — — 1 3 [3] (1 ejected: ≤3) — — 2 -1 [3,-1] [1, 3,-1] 3 3 -3 [3,-1,-3] [3,-1,-3] 3 4 5 [5] (front 3 expired; -3,-1 ejected) [-1,-3, 5] 5 5 3 [5,3] [-3, 5, 3] 5 6 6 [6] (3 and 5 ejected) [5, 3, 6] 6 7 7 [7] (6 ejected) [3, 6, 7] 7 answers: [3, 3, 5, 5, 6, 7] ``` (একই trace frame by frame আছে [visual-explanation.md](visual-explanation.md) section 7-এ।) **এটা কেন O(n), O(nk) না:** প্রতিটা index ঠিক একবার push হয় আর বড়জোর একবার pop হয় — হয় পেছন থেকে (নতুন কেউ এসে useless বানিয়ে দিল) অথবা সামনে থেকে (expired)। মোট deque operation ≤ 2n, কোনো একটা step যতগুলো ejection-ই ঘটাক না কেন। Naive approach-এর সাথে তুলনা করো: প্রতিটা window আবার scan করলে খরচ প্রতি window-তে O(k) → O(nk)। **মনে রাখার one-liner:** *deque হলো "কোনোদিন maximum হতে পারি"-দের waiting room; নতুন কারো কাছে dominated হলেই সাথে সাথে দরজা দেখিয়ে দেওয়া হয়।* **Variants:** comparison-টা উল্টে দাও sliding window **minimum**-এর জন্য; একই deque accelerate করে `dp[i] = max(dp[i-k..i-1]) + cost(i)` আকারের DP recurrence। **Representative problems:** - Sliding window maximum — [LeetCode 239](https://leetcode.com/problems/sliding-window-maximum/) — [Sliding Window Maximum: বাংলা নোট](problems/019-sliding-window-maximum.md) - Sum at least K-র shortest subarray (prefix sum-এর উপর monotonic deque) — [LeetCode 862](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/) — [Shortest Subarray with Sum at Least K: বাংলা নোট](problems/023-shortest-subarray-sum-k.md) - Constrained subsequence sum (deque-optimized DP) — [LeetCode 1425](https://leetcode.com/problems/constrained-subsequence-sum/) --- ## Pattern cheat sheet | Pattern | Killer trigger | One-line essence | | --- | --- | --- | | Matching / nesting | "valid", "nested", "undo" | stack = আমি এখন কীসের ভেতরে আছি | | BFS frontier | "shortest steps", "spreads" | FIFO order-টাই shortest-path-এর proof | | Design compositions | "implement X using Y", "O(1) min" | দরকারি history-টা একটা twin structure-এ maintain করো | | Monotonic stack | "next/previous greater/smaller" | নতুনরা যাদের হারায় তাদের সবাইকে answer deliver করে | | Monotonic deque | "max/min of every window" | dominated-দের eject করো; front-টাই সবসময় answer | ## দুটো monotonic pattern-এর সম্পর্ক দুটোই এক scan-এর মধ্যে একটা sorted "still relevant" collection maintain করে, আর দুটোই O(n) push-once/pop-once argument দিয়ে। পার্থক্যটা হলো *element কেন বের হয়*: | | Monotonic stack | Monotonic deque | | --- | --- | --- | | Element বের হয় কারণ... | নতুন কেউ তাদের হারিয়ে দেয় | নতুন কেউ তাদের হারিয়ে দেয় OR তারা window থেকে expire করে | | Exit-এর প্রান্ত | শুধু top | back (beaten) আর front (expired) | | Typical question | nearest greater/smaller neighbor | নড়তে থাকা window-র best value | এবার সবটা বানাও [implementation.py](./implementation.py)-তে, তারপর খোলো [problems/README.md](./problems/README.md)।