Problem link ও উৎস
- **Original source:** Classic k-way merge interview problem
- **Platform:** LeetCode —
- **Topic:** heaps + linked lists (merging)
- **Difficulty:** Hard
- **Pattern:** Heap over k frontiers
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **08 heaps** (k-টা list-এর মাথার মধ্যে সবচেয়ে ছোটটা O(log k)-তে তোলা), **03 linked lists** (node-এর pointer ধরে output list গড়া), আর **two-way merging** (দুটো sorted ধারা মেশানোর ধারণাকে k-ধারায় তোলা)। তিন জোড়া লাগলেই O(N log k) merge।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দেওয়া আছে `k`-টা linked list, প্রতিটাই আগে থেকে **sorted (ছোট থেকে বড়)**। সবগুলোকে মিশিয়ে একটা **single sorted linked list** বানাও আর তার head ফেরত দাও। কোনো list খালি থাকতে পারে, পুরো input-ও খালি হতে পারে।
```text
lists = [ 1->4->5 , 1->3->4 , 2->6 ]
merge : 1->1->2->3->4->4->5->6
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Edge case 1 (পুরো খালি): [] -> [] # কোনো list নেই
Edge case 2 (খালি list সহ): [[],[1]] -> [1] # খালি list বাদ পড়ে
Edge case 3 (একটা list): [[2,7,9]] -> [2,7,9]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো k-টা লাইনে লোক দাঁড়িয়ে, প্রতিটা লাইন উচ্চতা অনুযায়ী সাজানো (সামনে সবচেয়ে খাটো)। তুমি একটা মিলিত সারি বানাবে, সবার আগে সবচেয়ে খাটো। তুমি শুধু প্রতিটা লাইনের **সামনের জন**-কে দেখো, তাদের মধ্যে সবচেয়ে খাটোকে টেনে নাও, তার পেছনের জন এগিয়ে আসে। heap হলো তোমার "k সামনের লোকের মধ্যে সবচেয়ে খাটো কে" দ্রুত বলার যন্ত্র।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem তিনটা আগের chapter-এর tool জোড়া দেয়:
- **08 heaps** ([../../08-heap-priority-queue/](../../08-heap-priority-queue/README.md)) থেকে: k-টা list-এর বর্তমান মাথার মধ্যে সবচেয়ে ছোটটা প্রতিবার O(log k)-তে বের করা।
- **03 linked lists** ([../../03-linked-list/](../../03-linked-list/README.md)) থেকে: node-এর `next` pointer ধরে এগোনো আর dummy head দিয়ে output list গড়া।
- **two-way merging** ([পূর্বশর্ত](../../02-arrays-and-strings/README.md)) থেকে: "দুটো sorted ধারার মাথা তুলনা করে ছোটটা নাও" — এই two-way merge-এর ধারণা k-way-তে generalize করা।
একা merge দেয় "ছোটটা আগে" নিয়ম; একা heap দেয় k-এর মধ্যে minimum fast পাওয়া; linked list pointer দেয় output গাঁথা। তিন মিলে O(N log k)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: যেকোনো মুহূর্তে পরের output element অবশ্যই **k-টা list-এর বর্তমান মাথার মধ্যে সবচেয়ে ছোটটা** — কারণ প্রতিটা list sorted, তাই কোনো list-এর মাথার চেয়ে ছোট কিছু সেই list-এ আর নেই। তাই বারবার "k frontier-এর minimum" দরকার, ঠিক যেটা min-heap O(log k)-তে দেয়।
গণিত: একটা element pop করলে সেই list-এর পরের node push করি, heap সবসময় বড়জোর k element রাখে। মোট N element, প্রতিটায় O(log k) push+pop → O(N log k)। two-way merge k-1 বার করলেও O(N·k) হত; heap সেটা log-এ নামায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দরকার: **(a) একটা min-heap** যাতে k-টা list-এর মাথা থাকে, ছোট value আগে আসে (08 heaps), আর **(b) একটা dummy head + tail pointer** যাতে output linked list O(1)-তে append করা যায় (03 linked lists)। heap-এ tie ভাঙতে একটা counter রাখি (node সরাসরি compare না করতে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
min-heap (08) দেয় "k frontier-এর minimum" O(log k)-তে — array scan করলে প্রতিবার O(k) লাগত, মোট O(N·k)। dummy head + tail (04) দেয় O(1) append, প্রতিবার শেষ node খোঁজা ছাড়া। দুটো sorted list-এর pairwise merge (03)-কে k-way-তে তোলার জন্য heap-ই স্বাভাবিক, কারণ heap একই সাথে k-টা frontier-এর order ধরে রাখে। তাই heap + linked-list pointer-ই সবচেয়ে খাপ-খাওয়া জোড়া।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব list-এর সব value একটা array-তে ঢালো, array sort করো, তারপর সেই sorted value থেকে একটা নতুন linked list বানাও।
```text
vals = []
for lst in lists:
while lst: vals.append(lst.val); lst = lst.next
vals.sort()
# vals থেকে linked list গড়ো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব value জড়ো করে sort করা **O(N log N)** (N = মোট node)। এটা কাজ করে, কিন্তু input যে **আগে থেকেই sorted** সেই তথ্য নষ্ট করে — আমরা আবার সবকিছু পুরোপুরি sort করছি। heap-based merge সেই sortedness কাজে লাগিয়ে **O(N log k)** দেয়, আর k সাধারণত N-এর চেয়ে অনেক ছোট, তাই log k < log N। (পাশাপাশি brute force O(N) extra array নেয়।)
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পরের output element সবসময় k-টা list-এর মাথার মধ্যেই লুকিয়ে** — গোটা data নয়, শুধু k-টা frontier দেখলেই চলে। তাই পুরো N-কে বারবার না দেখে, প্রতি step-এ শুধু k-টা candidate-এর minimum বের করি; একটা নিলে সেই list-এর পরের node candidate হয়। min-heap এই "k-এর minimum, বারবার" কাজটার জন্যই তৈরি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা non-empty list-এর head heap-এ ঢালো (value দিয়ে compare, tie-তে counter)। তারপর loop: heap থেকে সবচেয়ে ছোট node pop করো, output tail-এ জোড়ো, আর সেই node-এর `next` থাকলে heap-এ push করো। heap খালি হলে শেষ — dummy head-এর পরের অংশই merged list। heap সবসময় ≤ k element রাখে, তাই প্রতিটা push/pop O(log k)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সবকিছু এক জায়গায় এনে sort করব" ভাবা ছাড়ো। ভাবো "প্রতি মুহূর্তে শুধু k-টা মাথা দেখলেই পরের element নিশ্চিত — দরকার শুধু k-এর minimum বারবার।" বিশাল sort একটা ছোট k-size heap-এর streaming pop-এ পরিণত হয়, sortedness কাজে লাগিয়ে।
### ছবিতে বোঝা {#7-visual-explanation}
```text
lists: 1->4->5 , 1->3->4 , 2->6
heap রাখে প্রতিটা list-এর মাথা:
step heap(values) pop output push (popped-এর next)
1 {1,1,2} 1 1 4 (list0)
2 {1,4,2} 1 1->1 3 (list1)
3 {4,3,2} 2 1->1->2 6 (list2)
4 {4,3,6} 3 1->1->2->3 4 (list1)
5 {4,4,6} 4 1->1->2->3->4 5 (list0)
6 {5,4,6} 4 1->1->2->3->4->4 (list1 শেষ)
7 {5,6} 5 1->1->2->3->4->4->5 (list0 শেষ)
8 {6} 6 1->1->2->3->4->4->5->6 (list2 শেষ)
ফল: 1->1->2->3->4->4->5->6
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`lists = [1->4->5, 1->3->4, 2->6]`:
1. heap-এ মাথা: (1,list0),(1,list1),(2,list2)
2. pop (1,list0) → output 1; push (4,list0). heap: {1,2,4}
3. pop (1,list1) → 1->1; push (3,list1). heap: {2,3,4}
4. pop (2,list2) → 1->1->2; push (6,list2). heap: {3,4,6}
5. pop (3) → ...->3; push 4. pop (4,list1) → ...->4; list1 শেষ। pop (4,list0) → ...->4; push 5
6. pop (5) → ...->5; list0 শেষ। pop (6) → ...->6; list2 শেষ → heap খালি
7. return dummy.next = 1->1->2->3->4->4->5->6
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def merge_k_lists(lists):
heap = [] # 08 heaps: (value, tie, node)
counter = 0 # tie-breaker, node compare এড়াতে
for node in lists: # প্রতিটা list-এর মাথা ঢালো
if node:
heapq.heappush(heap, (node.val, counter, node))
counter += 1
dummy = ListNode() # 03 linked lists: dummy head
tail = dummy
while heap:
_, _, node = heapq.heappop(heap) # k frontier-এর minimum
tail.next = node # output-এ জোড়ো
tail = node
if node.next: # সেই list-এর পরের node candidate
heapq.heappush(heap, (node.next.val, counter, node.next))
counter += 1
return dummy.next
# ---- helpers (test-এর জন্য) ----
def build(vals):
dummy = ListNode()
cur = dummy
for v in vals:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
# ---- tests ----
assert to_list(merge_k_lists([build([1,4,5]), build([1,3,4]), build([2,6])])) == [1,1,2,3,4,4,5,6]
assert to_list(merge_k_lists([])) == [] # পুরো খালি
assert to_list(merge_k_lists([build([]), build([1])])) == [1] # খালি list বাদ
assert to_list(merge_k_lists([build([2,7,9])])) == [2,7,9] # একটা list
assert to_list(merge_k_lists([build([]), build([])])) == [] # সব খালি
assert to_list(merge_k_lists([build([5]), build([1]), build([3])])) == [1,3,5]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `heap = []` / `counter` — min-heap; tuple-এ value আগে compare হয়, value সমান হলে `counter` tie ভাঙে যাতে কখনো `ListNode` compare না হয় (নাহলে TypeError)।
- প্রথম `for node in lists` — প্রতিটা non-empty list-এর head heap-এ; heap-এ এখন ≤ k element (08 heaps)।
- `dummy = ListNode(); tail = dummy` — dummy head দিয়ে edge case ছাড়াই output গড়া, tail-এ O(1) append (03 linked lists)।
- `while heap` — heap খালি না হওয়া পর্যন্ত চলো।
- `heappop` — k frontier-এর সবচেয়ে ছোট node, O(log k)।
- `tail.next = node; tail = node` — সেই node-কে output-এর শেষে জোড়ো।
- `if node.next: heappush(...)` — যেই list থেকে node নিলাম, তার পরের node নতুন candidate (two-way merging-এর "ধারা এগিয়ে নাও")।
- `return dummy.next` — merged sorted list-এর head।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
তিন list-এর example-এ heap বারবার সবচেয়ে ছোট মাথা তুলে 1,1,2,3,4,4,5,6 বানায় → assert pass। খালি input-এ heap শুরুতেই খালি → dummy.next None → []; খালি list বাদ পড়ে [1]; একটা/সব-খালি/তিন-singleton case-ও সঠিক। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(N log k)** — N = মোট node; প্রতিটা node ঠিক একবার heap-এ push আর একবার pop, heap-এ সর্বদা ≤ k element তাই প্রতি op O(log k)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — heap বড়জোর k element ধরে (প্রতিটা list থেকে একটা মাথা); output list reuse করছে input node, তাই extra node তৈরি হয় না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- heap-এ শুধু node ঢালা (value tie-breaker ছাড়া) — value সমান হলে Python `ListNode` compare করতে গিয়ে crash; `(val, counter, node)` tuple দাও।
- pop করা node-এর `next` heap-এ push করতে ভুলে যাওয়া — তখন সেই list-এর বাকি অংশ হারিয়ে যায়।
- dummy head না রাখা — প্রথম node সামলাতে আলাদা special-case bug সহজ।
- সব value জড়ো করে sort করা (brute) — কাজ করে কিন্তু sortedness নষ্ট করে O(N log N); heap দিয়ে O(N log k) করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: min-heap দিয়ে বারবার minimum তোলা (08 heaps-এর [../../08-heap-priority-queue/](../../08-heap-priority-queue/README.md)) + linked list pointer আর dummy-head দিয়ে list গড়া (03-এর [../../03-linked-list/](../../03-linked-list/README.md)) + দুটো sorted list merge করার ধারণা (array ও merge-এর [পূর্বশর্ত](../../02-arrays-and-strings/README.md))। দুই-list merge cold অবস্থায় জানা থাকলে heap দিয়ে এটাই k-way-তে বাড়ে। ([../hard-patterns.md](../hard-patterns.md)-এর combo 3-এর "always need the smallest frontier" instinct।)
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge Two Sorted Lists (এই problem-এর two-way ভিত্তি; heap ছাড়া) —