Problem link ও উৎস
- **Original source:** Classic k-way merge over sorted rows
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** K-way merge (প্রতি row-এ একটা cursor)
- **Basic idea inherited from:** `08` k-way merge — k sorted list একসাথে merge
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `n x n` matrix দেওয়া, যেখানে **প্রতিটা row বাম-থেকে-ডান sorted** আর **প্রতিটা column উপর-থেকে-নিচ sorted**। তোমাকে পুরো matrix-এর সব সংখ্যার মধ্যে **k-তম সবচেয়ে ছোট** সংখ্যাটা বের করতে হবে। মনে রেখো এটা *sorted order-এ k-তম*, distinct নয় — duplicate থাকলে তারাও আলাদা করে গোনা হয়।
```text
matrix = [[1, 5, 9],
[10, 11, 13],
[12, 13, 15]], k = 8 -> 13
```
### Input ও output {#8-example-input-and-output}
```text
Input : matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 -> Output: 13
Input : matrix = [[-5]], k = 1 -> Output: -5
Input : matrix = [[1,2],[1,3]], k = 2 -> Output: 1 (duplicate গোনা হয়)
Input : matrix = [[1,2],[1,3]], k = 4 -> Output: 3
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো n-টা আলাদা queue, প্রতিটা ভেতরে আগে-থেকে ছোট-থেকে-বড় সাজানো লোকজন। একজন officer প্রতিবার সব queue-এর **সামনের লোকদের** দেখে সবচেয়ে ছোট number-ওয়ালাকে ডাকেন; ওই queue তখন এক ধাপ এগোয়। k-তম বার যাকে ডাকা হলো, সে-ই উত্তর। officer-এর চোখে শুধু n-টা front — পুরো ভিড় না; সেই চোখটাই heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত `08`-এর **k-way merge**। প্রতিটা row নিজে একটা sorted list; তুমি যদি সব row একসাথে merge করতে থাকো, sorted order-এ একটা একটা করে element বের হবে — k-তম বার যেটা বেরোয় সেটাই উত্তর। পুরো merge শেষ করার দরকার নেই, প্রথম k-টা element হলেই থামবে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **overall sorted sequence-এর পরের element সবসময় কোনো না কোনো row-cursor যেদিকে দেখাচ্ছে তার মধ্যে সবচেয়ে ছোট।** Row sorted বলে একটা row থেকে শুধু তার বর্তমান cursor-value-ই candidate; সব row-এর candidate-দের মধ্যে min-টাই next। এই min বারবার পেতে heap, আর প্রতিবার সেই row-এর cursor এক ঘর ডানে সরাও।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap of triples** `(value, row, col)` — প্রতিটা active row-এর current cursor value ধরে রাখে। সাথে matrix-টা তো আছেই, cursor advance করতে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
heap-এ কখনো n-টার (row সংখ্যা) বেশি entry থাকে না — প্রতি row-এর একটা cursor। smallest-টা peek করা O(1)-এর মতো (top), pop/push O(log n)। তাই k-তম element পেতে O(k log n) — পুরো n² element sort করার (O(n² log n)) দরকার নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: পুরো matrix-এর সব সংখ্যা একটা flat list-এ ঢালো, list-টা sort করো, তারপর `(k-1)`-তম index নাও।
```text
সব নাও -> [1,5,9,10,11,12,13,13,15] -> sort -> index 7 (k=8) -> 13
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
সব n² element collect করে sort করা মানে **O(n² log n)** time আর O(n²) extra space। অথচ আমাদের row/column sortedness ব্যবহারই করা হলো না, আর আমাদের পুরো order লাগেও না — শুধু প্রথম k-টা। তাই পুরো matrix sort করা অপচয়, বিশেষত k ছোট হলে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পুরো sequence sort না করেও**, k-way merge দিয়ে শুধু প্রথম k-টা element বের করা যায়। প্রতিটা row sorted বলে heap-এ একসাথে n-টার বেশি candidate লাগে না। আরও smart approach (binary search on value) O(n log(max−min))-এও পারে, কিন্তু heap version-টা সবচেয়ে সরাসরি k-way merge।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা row-এর প্রথম element `(value, row, 0)` দিয়ে একটা min-heap বানাও। k বার এই কাজ করো: top pop করো; যদি সেই row-এ আরও element থাকে, পরের `(value, row, col+1)` push করো। k-তম pop-এর value-ই উত্তর। n-row-এর জায়গায় শুধু প্রথম row নিয়ে শুরু করলেও চলে (column sorted বলে), তবে সব row দিয়ে শুরু করা সহজ আর নিরাপদ।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "2D matrix-এ k-তম" না ভেবে ভাবো "n-টা sorted list (row) merge করছি, k-তম element-এ থামছি।" "sorted rows/columns / k sorted ... / matrix-এ kth smallest" — এই কথাগুলো শুনলেই k-way merge heap-এর আলো জ্বলা উচিত, ঠিক যেমন Merge k Sorted Lists-এ (#17)।
### ছবিতে বোঝা {#7-visual-explanation}
`matrix = [[1,5,9],[10,11,13],[12,13,15]]`, k=8 — heap-এ প্রতি row-এর প্রথম element দিয়ে শুরু:
```text
heap (value,row,col): (1,0,0) (10,1,0) (12,2,0)
pop 1 (row0) -> push (5,0,1) count 1
pop 5 (row0) -> push (9,0,2) count 2
pop 9 (row0) -> row শেষ count 3
pop 10 (row1) -> push (11,1,1) count 4
pop 11 (row1) -> push (13,1,2) count 5
pop 12 (row2) -> push (13,2,1) count 6
pop 13 (row1,col2) -> row1 শেষ; কিছু push নয় count 7
pop 13 (row2,col1) -> অষ্টম pop-এই উত্তর 13; থামো count 8
আরও চালালে row2-এর পরের value (15,2,2) push হতো।
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `matrix = [[1,2],[1,3]]`, k=4:
1. heap = {(1,0,0), (1,1,0)} (প্রতি row-এর প্রথম element)
2. pop (1,0,0) → count 1; row0-এ col1 আছে → push (2,0,1); heap {(1,1,0),(2,0,1)}
3. pop (1,1,0) → count 2; row1-এ col1 আছে → push (3,1,1); heap {(2,0,1),(3,1,1)}
4. pop (2,0,1) → count 3; row0 শেষ; heap {(3,1,1)}
5. pop (3,1,1) → count 4 → k-তম → return 3
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def kth_smallest(matrix, k):
n = len(matrix)
# প্রতি row-এর প্রথম element: (value, row, col)
heap = [(matrix[r][0], r, 0) for r in range(n)]
heapq.heapify(heap) # top = সব cursor-এর মধ্যে smallest
val = None
for _ in range(k): # k বার merge-step
val, r, c = heapq.heappop(heap)
if c + 1 < len(matrix[r]): # ওই row-এ আরও element আছে?
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
return val # k-তম pop করা value
# ---- tests ----
m1 = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]
assert kth_smallest(m1, 8) == 13
assert kth_smallest([[-5]], 1) == -5 # একটাই element
m2 = [[1, 2], [1, 3]]
assert kth_smallest(m2, 1) == 1
assert kth_smallest(m2, 2) == 1 # duplicate গোনা হয়
assert kth_smallest(m2, 3) == 2
assert kth_smallest(m2, 4) == 3
m3 = [[1, 3, 5], [6, 7, 12], [11, 14, 14]]
assert kth_smallest(m3, 6) == 11
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `n = len(matrix)` — row সংখ্যা (square matrix বলে column সংখ্যাও n, তবে কোডে `len(matrix[r])` ধরে নিরাপদ)।
- `heap = [(matrix[r][0], r, 0) ...]` — প্রতি row-এর প্রথম element, সাথে row index আর col index।
- `heapq.heapify(heap)` — O(n)-এ heap; top = সব cursor-এর smallest value।
- `for _ in range(k):` — ঠিক k বার smallest টানব।
- `val, r, c = heappop(heap)` — এখনকার smallest cursor value আর তার অবস্থান।
- `if c + 1 < len(matrix[r]): heappush(...)` — ওই row-এ পরের element থাকলে cursor advance করে heap-এ ঢালো।
- `return val` — loop শেষে `val` হলো k-তম pop করা value, অর্থাৎ উত্তর।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`kth_smallest([[1,2],[1,3]], 4)` section 14-এর dry run মেনে 3 দেয় — assert pass। বড় matrix `m1`-এ k=8 → 13; single-cell `[[-5]]` → -5; duplicate-ভরা `m2`-তে k=1,2 দুটোই 1 (duplicate আলাদা গোনা হয়)। order এখানে fixed (k-তম মানে নির্দিষ্ট), তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(k log n)** — n = row সংখ্যা; heap-এ কখনো n-টার বেশি entry না, আর আমরা k বার pop/push করি (প্রতিটা O(log n))। heapify O(n)। সাধারণত k ≤ n² বলে এটা naive O(n² log n)-এর থেকে ভালো, বিশেষত ছোট k-তে।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — heap-এ বড়জোর n-টা cursor entry (প্রতি row একটা)। flat-list-sort approach যেখানে O(n²) লাগত, তার তুলনায় এটা অনেক কম memory।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- প্রতি row-এর শুধু প্রথম element-ই push না করা / ভুল index দেওয়া — তখন merge ভেঙে যায়।
- duplicate-কে distinct ভেবে বাদ দেওয়া — kth smallest মানে multiset-এ kth, distinct নয়।
- column-sorted property-কে row-sorted ভেবে গুলিয়ে ফেলা — এখানে আমরা row ধরে merge করছি, তাই row-cursor-ই advance করতে হবে।
- k-তম pop-এর আগে থেমে যাওয়া বা একবার বেশি pop করা — ঠিক `range(k)` লুপ চালাও।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর `patterns.md`-র Pattern 2 (K-way merge) — "k-টা cursor-value heap-এ রাখো, smallest pop করো, সেই cursor advance করো"। এটা merge sort-এর two-pointer merge-এরই k-pointer রূপ, যেখানে কোন pointer নড়বে সেটা heap ঠিক করে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge k Sorted Lists —