Problem link ও উৎস
- **Original source:** Classic k-way merge with a coverage window
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Hard
- **Pattern:** K-way merge (min-heap of frontiers) + tracking the current max → window
- **Basic idea inherited from:** `02-arrays-and-strings` sliding window + `08` k-way merge
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`k`-টা list দেওয়া আছে, প্রতিটা **বাড়তে থাকা (sorted)** ক্রমে সাজানো। তোমাকে এমন একটা ছোট range `[a, b]` খুঁজতে হবে যেটার ভেতরে **প্রতিটা list থেকে অন্তত একটা করে সংখ্যা** পড়ে। range যত ছোট (`b - a` যত কম) তত ভালো; tie হলে যে range-এর `a` ছোট সেটা নাও। সেই `[a, b]` return করো।
```text
[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] -> [20, 24]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] -> Output: [20, 24]
Input : [[1,2,3],[1,2,3],[1,2,3]] -> Output: [1, 1] (সব মিলে যায়)
Input : [[10],[11]] -> Output: [10, 11]
Input : [[1,10,11],[20,30]] -> Output: [11, 20]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো `k`-টা দৌড়বিদ, প্রত্যেকে নিজের track-এ সামনে এগোচ্ছে (sorted)। তুমি চাও এক মুহূর্ত যেখানে সবাই একে অপরের যত কাছাকাছি সম্ভব। সবচেয়ে **পিছিয়ে থাকা** দৌড়বিদকে এক পা সামনে এগিয়ে দাও (তার পরের checkpoint-এ) — এতে দলটা কুঁকড়ে আসে, আর সবচেয়ে এগিয়ে থাকা জন তো পিছায় না। প্রতিবার দলের "ছড়ানো" (max − min) মেপে রাখো; কোনো একজন track শেষ করলে খেলা শেষ। "সবচেয়ে পিছিয়ে থাকাকে চট করে দাও" — সেই যন্ত্রই min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত দুটো জিনিসের জোড়: `08`-এর **k-way merge** (প্রতিটা list-এর সামনের element নিয়ে একটা min-heap, বারবার সবচেয়ে ছোটটা টানা — যেমন `012`/`017`-এ), আর `02-arrays-and-strings`-এর **sliding window** চিন্তা (একটা window যেটার ভেতরে সব list "covered" থাকে)। এখানে window-টা সরাসরি index-এর না, বরং প্রতিটা list থেকে একটা করে value নিয়ে গড়া।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: যদি প্রতিটা list থেকে ঠিক একটা করে value বেছে নাও, তাহলে সেই k-টা value-এর `[min, max]`-ই একটা valid range। তুমি চাও `max - min` ছোট করতে। min-টা যে list থেকে এসেছে, সেই list-এ একটু **বড়** value-এ এগোলে min বাড়ে (range সঙ্কুচিত হওয়ার সুযোগ), কিন্তু max কখনো কমে না। তাই বারবার বর্তমান min-কে তার পরের element দিয়ে replace করে min বাড়াও, প্রতিবার `[min, max]` মেপে রাখো — কোনো list শেষ হলে থামো।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap** (k-way merge frontier)। প্রতিটা entry `(value, list_index, element_index)` — কোন list-এর কোন position থেকে এসেছে তা মনে রাখার জন্য। সাথে একটা সাধারণ variable `current_max` — heap-এ এই মুহূর্তে থাকা সব value-এর মধ্যে সবচেয়ে বড়টা।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতি step-এ তোমার দরকার শুধু **বর্তমান minimum** (যাকে এগিয়ে দিলে window সঙ্কুচিত হতে পারে)। min-heap সেটা top-এ O(1)-এ দেয়, pop/push O(log k)। max আলাদা variable-এ রাখা সস্তা, কারণ নতুন value push করার সময়ই সেটা update করা যায়। পুরো merged sequence কখনো বানাতে হয় না — heap-এ একসাথে বড়জোর k-টা element থাকে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা list থেকে একটা করে value-এর সব combination বানাও, প্রতিটার `[min, max]` মাপো, সবচেয়ে ছোট range রাখো।
```text
ছোট example: L0=[1,4], L1=[2,6]
choices: (1,2)->width 1; (1,6)->width 5; (4,2)->width 2; (4,6)->width 2
সব combination-এর মধ্যে best range [1,2]
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা list-এর length যদি গড়ে m হয়, combination-সংখ্যা **O(mᵏ)** — exponential, k একটু বড় হলেই অসম্ভব। অথচ আমাদের সব combination দেখার দরকার নেই: কেবল min-কে এগিয়ে যাওয়াটাই range সঙ্কুচিত করার একমাত্র productive move, তাই smart traversal-এ O(n log k)-তে নামা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: একটা valid window-এ window সঙ্কুচিত করার একমাত্র উপায় হলো **বর্তমান minimum-কে বড় করা** — অর্থাৎ যে list থেকে min এসেছে সেই list-এ পরের element-এ যাওয়া। max কমানোর কোনো উপায় নেই (সেটা শুধু বাড়ে), তাই min-কে যতটা সম্ভব max-এর কাছে টেনে আনাই খেলা। আর min সবসময় heap-এর top-এ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা list-এর প্রথম element নিয়ে min-heap বানাও, `current_max` = তাদের সর্বোচ্চ। Loop: top (current min) pop করো; `[min, current_max]` যদি আগের best-এর চেয়ে ছোট হয়, best update করো। সেই list-এ পরের element থাকলে push করো (আর `current_max` দরকারমতো update করো); না থাকলে থামো — ওই list আর কোনো value দিতে পারবে না, তাই কোনো future window সম্পূর্ণ হবে না। মোট O(n log k)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "smallest range" না ভেবে ভাবো "k-টা sorted stream একসাথে merge করছি, আর প্রতি মুহূর্তে heap-এ থাকা k-টা frontier value-ই আমার current window।" min এগোলে window নড়ে। "প্রতিটা group থেকে অন্তত একটা cover করতে হবে, sorted lists" — শুনলেই k-way-merge-min-heap + একটা running max মাথায় আনবে।
### ছবিতে বোঝা {#7-visual-explanation}
Lists: `L0=[4,10,15,24,26]`, `L1=[0,9,12,20]`, `L2=[5,18,22,30]`। নিচে frontier-এর column-গুলো **list order-এ**, heap-এর internal array order-এ নয়। প্রতি row-তে তিন list-ই represented।
| L0 | L1 | L2 | বর্তমান range | পরের কাজ | এখন পর্যন্ত best |
| --- | --- | --- | --- | --- | --- |
| 4 | 0 | 5 | [0,5], width 5 | L1: 0→9 | [0,5] |
| 4 | 9 | 5 | [4,9], width 5 | L0: 4→10 | [0,5] |
| 10 | 9 | 5 | [5,10], width 5 | L2: 5→18 | [0,5] |
| 10 | 9 | 18 | [9,18], width 9 | L1: 9→12 | [0,5] |
| 10 | 12 | 18 | [10,18], width 8 | L0: 10→15 | [0,5] |
| 15 | 12 | 18 | [12,18], width 6 | L1: 12→20 | [0,5] |
| 15 | 20 | 18 | [15,20], width 5 | L0: 15→24 | [0,5] |
| 24 | 20 | 18 | [18,24], width 6 | L2: 18→22 | [0,5] |
| 24 | 20 | 22 | [20,24], width 4 | L1 শেষ; থামুন | [20,24] |
Width সমান হলে ছোট left boundary জেতে, তাই প্রথম কয়েকটি width-5 range [0,5]-কে সরায়নি। শেষ row-তে range ছোট হয়েছে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[[1,10,11],[20,30]]`:
1. frontier min-heap: (1, L0, idx0), (20, L1, idx0); current_max = 20
2. best = কিছু না (∞ width)
3. pop (1, L0): window [1, 20], width 19 → best = [1, 20]; L0-এ পরের 10 push; current_max = max(20, 10) = 20
4. pop (10, L0): window [10, 20], width 10 < 19 → best = [10, 20]; L0-এ পরের 11 push; current_max = 20
5. pop (11, L0): window [11, 20], width 9 < 10 → best = [11, 20]; L0-এ পরের element নেই → থামো
6. return [11, 20]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def smallest_range(nums):
# প্রতিটা list-এর প্রথম element নিয়ে frontier min-heap: (value, list_idx, elem_idx)
heap = [(rows[0], i, 0) for i, rows in enumerate(nums)]
heapq.heapify(heap)
current_max = max(rows[0] for rows in nums) # frontier-এর সর্বোচ্চ
best_lo, best_hi = heap[0][0], current_max # একটা valid window দিয়ে শুরু
while True:
val, li, ei = heapq.heappop(heap) # বর্তমান minimum
if current_max - val < best_hi - best_lo: # আরও ছোট window?
best_lo, best_hi = val, current_max
if ei + 1 == len(nums[li]): # এই list শেষ -> আর cover সম্ভব না
break
nxt = nums[li][ei + 1] # একই list-এ পরের element
current_max = max(current_max, nxt) # max শুধু বাড়তে পারে
heapq.heappush(heap, (nxt, li, ei + 1))
return [best_lo, best_hi]
# ---- tests ----
assert smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]) == [20, 24]
assert smallest_range([[1,2,3],[1,2,3],[1,2,3]]) == [1, 1] # সব মিলে যায়
assert smallest_range([[10],[11]]) == [10, 11]
assert smallest_range([[1,10,11],[20,30]]) == [11, 20]
assert smallest_range([[5]]) == [5, 5] # একটাই list, একটাই value
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `heap = [(rows[0], i, 0) for i, rows in enumerate(nums)]` — প্রতিটা list-এর প্রথম element, সাথে `(list index, element index)` যাতে জানি কোথা থেকে এলো।
- `heapq.heapify(heap)` — O(k)-এ min-heap; top সবসময় frontier-এর সবচেয়ে ছোট value।
- `current_max = max(...)` — frontier-এ এই মুহূর্তে থাকা সব value-এর সর্বোচ্চ; window-এর উপরের প্রান্ত।
- `best_lo, best_hi = heap[0][0], current_max` — শুরুতেই একটা valid window (min ও max) রেখে দিই, পরে ছোট পেলে update।
- `val, li, ei = heapq.heappop(heap)` — বর্তমান minimum আর সে কোন list-এর কোন position।
- `if current_max - val < best_hi - best_lo:` — `[val, current_max]` আগের best-এর চেয়ে সরু হলে best update।
- `if ei + 1 == len(nums[li]): break` — যে list থেকে min এলো সেটা শেষ → আর এগোনো গেলে ওই list cover হবে না, তাই থামো।
- `current_max = max(current_max, nxt)` — নতুন value push-এর আগে max দরকারমতো বাড়াও (কখনো কমে না)।
- `heapq.heappush(heap, (nxt, li, ei + 1))` — একই list-এর পরের element frontier-এ আনো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`smallest_range([[1,10,11],[20,30]])` section 14-এর dry run মেনে [11, 20] দেয় — assert pass। প্রথম বড় example-এ frontier ধীরে ধীরে এগিয়ে [20, 24]-এ সবচেয়ে সরু window পায়। `[[1,2,3]] x3`-এ শুরুতেই সব list-এ 1 আছে → [1, 1]। `[[10],[11]]` → শুরুর frontier-ই উত্তর [10, 11]। single list `[[5]]` → একটাই value [5, 5]। range একটা নির্দিষ্ট জোড়া, তাই সরাসরি list-সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log k)** — মোট n-টা element (সব list মিলে), প্রতিটা বড়জোর একবার push/pop হয় (প্রতিটা O(log k), কারণ heap-এ সর্বদা ≤ k entry)। heapify O(k)। তাই dominant term O(n log k)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — heap-এ একসাথে ঠিক k-টা entry (প্রতিটা list থেকে একটা)। আউটপুট ছাড়া বাড়তি memory heap-সমান, input-এর মোট আকারের উপর নির্ভর করে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `current_max` track না করা, প্রতিবার heap-এর সব ঘেঁটে max বের করা — এতে step-প্রতি O(k) যোগ হয়, অযথা ধীর।
- কোন list থেকে value এলো (`list_idx`) tuple-এ না রাখা — তখন পরের element কোথা থেকে push করবে জানবে না।
- list শেষ হলে `break` না দেওয়া — খালি index access করে IndexError, বা ভুলভাবে অসম্পূর্ণ window গোনা।
- tie-breaking ভুল করা — "strictly smaller width হলে তবেই update" রাখলে প্রথম (সবচেয়ে ছোট `a`-ওয়ালা) best আপনাআপনি ধরে থাকে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর `patterns.md`-র Pattern 4 (K-way merge — প্রতিটা sorted source-এর frontier একটা min-heap-এ, বারবার ছোটটা টানো) — যেমন `012` Kth Smallest in Sorted Matrix আর `017` Merge k Sorted Lists। তার সাথে `02-arrays-and-strings`-এর sliding-window "একটা valid window সঙ্কুচিত করো" idea মিশেছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge k Sorted Lists —