Problem Tracker — Stack and Queue¶
এই topic-এর working list, মোটামুটি easy → hard order-এ সাজানো। প্রতিটা row solve করার সাথে সাথে নিজের আলাদা note file হয়ে যায়; প্রতিটা full note ../../templates/ds-problem-note-template.md-এর 24-section template মেনে চলে — শুরু করার সময় template-টা list-এ দেওয়া note file-এ copy করে নাও। নিচের description গুলো আমাদের নিজেদের ভাষায়; official statement link-এর পেছনে।
এই tracker কীভাবে ব্যবহার করবে:
- Problem 1, 9 আর 19 হলো মেরুদণ্ড: matching, monotonic stack, monotonic deque। বাকি সবকিছু এদের চারপাশে ঘোরে।
Statusupdate করো: planned → attempted → solved → reviewed।- "Inherits from" column বলে দেয় প্রতিটা problem গোপনে আগের কোন idea reuse করছে — code লেখার আগে সেটার নাম বলো।
| # | Problem | Difficulty | Source | Pattern | Inherits from | Note file | Status |
|---|---|---|---|---|---|---|---|
| 1 | Bracket গুলো কি ঠিকভাবে nested? | Easy | LeetCode 20 | Matching (stack) | Raw push/pop discipline | 001-valid-parentheses.md | planned |
| 2 | Add/double/cancel op দিয়ে একটা score list রাখো | Easy | LeetCode 682 | Stack simulation | Push/pop as undo | 002-baseball-game.md | planned |
| 3 | Backspace সহ type করা দুটো string compare করো | Easy | LeetCode 844 | Stack simulation | Matching/undo (problem 1) | 003-backspace-compare.md | planned |
| 4 | দুটো stack দিয়ে একটা FIFO queue বানাও | Easy | LeetCode 232 | Design (two stacks) | Dynamic array-র amortized analysis (../../02-arrays-and-strings/) | 004-queue-via-stacks.md | planned |
| 5 | Queue দিয়ে একটা LIFO stack বানাও | Easy | LeetCode 225 | Design | Problem 4, mirror করা | 005-stack-via-queues.md | planned |
| 6 | O(1) minimum lookup সহ stack | Easy | LeetCode 155 | Design (twin stack) | "Maintain the needed history" tweak | 006-min-stack.md | planned |
| 7 | ডানদিকের প্রথম strictly greater value (helper map সহ) | Easy | LeetCode 496 | Monotonic stack | Matching: "most recent unresolved" | 007-next-greater-i.md | planned |
| 8 | একটা postfix expression evaluate করো | Medium | LeetCode 150 | Stack simulation | Operand-রা stack-এ অপেক্ষা করে যতক্ষণ না তাদের operator আসে | 008-evaluate-rpn.md | planned |
| 9 | প্রতি দিনের জন্য, কত দিন পর গরম temperature | Medium | LeetCode 739 | Monotonic stack | Problem 7, value-র বদলে distance নিয়ে | 009-daily-temperatures.md | planned |
| 10 | 3[a2[c]]-এর মতো nested encoded string expand করো | Medium | LeetCode 394 | Nesting (stack of contexts) | Matching (1) + string building (../../02-arrays-and-strings/) | 010-decode-string.md | planned |
| 11 | মুখোমুখি সংঘর্ষে কোন asteroid গুলো বাঁচে? | Medium | LeetCode 735 | Stack simulation | Monotonic flavor: নতুনরা dominated-দের ধ্বংস করে | 011-asteroid-collision.md | planned |
| 12 | একটা grid-এ connected land region count করো | Medium | LeetCode 200 | BFS frontier (queue) | Queue discipline; full theory ../../09-graphs/-এ | 012-number-of-islands.md | planned |
| 13 | সব কমলায় পচন ছড়াতে কত মিনিট | Medium | LeetCode 994 | Multi-source BFS | Problem 12, একসাথে কয়েকটা start নিয়ে | 013-rotting-oranges.md | planned |
| 14 | একটা binary tree-র level-by-level value | Medium | LeetCode 102 | BFS (queue), layered | Queue-র layer guarantee + len-snapshot trick | 014-level-order-traversal.md | planned |
| 15 | Array ঘুরে গেলে (wrap করলে) next greater element | Medium | LeetCode 503 | Monotonic stack (circular) | Problem 9 + array-দুবার-scan trick | 015-next-greater-ii.md | planned |
| 16 | পরপর কত দিন price বেশি ছিল না (streaming) | Medium | LeetCode 901 | Monotonic stack (online) | Problem 9, একটা একটা করে value আসছে | 016-stock-span.md | planned |
| 17 | প্রতিটা subarray-র minimum-এর যোগফল | Medium | LeetCode 907 | Monotonic stack + contribution | Math level 5-এর contribution technique (prefix-difference-contribution) | 017-sum-subarray-minimums.md | planned |
| 18 | একটা Unix-style file path simplify করো | Medium | LeetCode 71 | Stack simulation | ".." pop করে, নাম push করে — ছদ্মবেশে undo | 018-simplify-path.md | planned |
| 19 | Size k-এর প্রতিটা sliding window-র maximum | Hard | LeetCode 239 | Monotonic deque | Sliding window basic (../../02-arrays-and-strings/) + queue; full walkthrough ../patterns.md Pattern 5-এ | 019-sliding-window-maximum.md | planned |
| 20 | একটা histogram-এর নিচে largest rectangle | Hard | LeetCode 84 | Monotonic stack | Problem 9-এর previous/next-smaller machinery | 020-largest-rectangle.md | planned |
| 21 | Bar-গুলোর মাঝে আটকে থাকা পানি (stack solution) | Hard | LeetCode 42 | Monotonic stack variant | Problem 20-এর geometry + bounded-by-neighbors idea | 021-trapping-rain-water-stack.md | planned |
| 22 | +, -, parentheses সহ একটা expression evaluate করো | Hard | LeetCode 224 | Nesting (stack of contexts) | Problem 10-এর save-context-on-( restore-on-) move | 022-basic-calculator.md | planned |
| 23 | Sum at least K-র shortest subarray (negative allowed) | Hard | LeetCode 862 | Monotonic deque on prefix sums | Problem 19-এর deque + math level 5-এর prefix sums | 023-shortest-subarray-sum-k.md | planned |
Suggested milestones (পরামর্শ দেওয়া milestone)¶
- 1–7-এর পর: stack discipline আর design trick গুলো তোমার।
- 8–18-এর পর: monotonic-stack trigger গুলো ("next greater", "span", "until a warmer day") দেখা মাত্র চিনে ফেলো, আর BFS-with-queue automatic হয়ে গেছে।
- 19–23-এর পর: hard tier। Problem 19 হলো chapter-এর centerpiece — তার deque invariant-টা scratch থেকে re-derive করতে পারলে ("নতুন আসা element-এর চেয়ে ছোট সবাইকে eject করো; front-টাই সবসময় max"), এই chapter complete।