Skip to content

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?

'(' 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:

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:

enqueue S with d=0
pop S(0): enqueue unvisited neighbors with d=1
pop each 1: enqueue their unvisited neighbors with d=2
...
the moment T is popped, its d is THE shortest distance — guaranteed,
because no d=3 cell can leave the queue before every d=2 cell has.
Mark cells visited when PUSHED (not popped) to avoid duplicates.

Inherits from: সাধারণ queue discipline। Full treatment (graphs, multi-source BFS, 0-1 BFS) থাকে ../09-graphs/-এ — এই chapter শুধু তাকে সঠিক container-টা ধরিয়ে দেয়।

Representative problems:

  • Connected region count করো (BFS flood fill) — LeetCode 200
  • ছড়াতে থাকা process, শেষ হতে কত মিনিট — LeetCode 994
  • Binary tree-র level-order traversal — LeetCode 102

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 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:

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/) — কালেভদ্রে একটা বড় cost দাও, সেটা অনেকগুলো সস্তা operation-এর ঘাড়ে চাপাও।

Representative problems:

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:

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/-এ আর LeetCode 907।

Representative problems:

  • কত দিন পর গরম temperature — LeetCode 739
  • Histogram-এর largest rectangle — LeetCode 84
  • Sum of subarray minimums (monotonic stack + contribution) — LeetCode 907

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।

কী থেকে inherit করে: ../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-এর জন্য:

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:

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 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
  • Sum at least K-র shortest subarray (prefix sum-এর উপর monotonic deque) — LeetCode 862
  • Constrained subsequence sum (deque-optimized DP) — LeetCode 1425

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-তে, তারপর খোলো problems/README.md।