019 — Merge k Sorted Lists¶

Problem link ও উৎস

Original source: Classic linked list exercise
Platform: LeetCode — https://leetcode.com/problems/merge-k-sorted-lists/
Topic: linked list
Difficulty: Hard
Pattern: merge + min-heap (priority queue)
Basic idea inherited from: problem 2 (merge two) scale করা; heap-এর preview

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

k-টা linked list দেওয়া, প্রতিটাই আলাদাভাবে sorted (ছোট-থেকে-বড়)। তোমাকে এদের সবগুলোকে একটাই sorted list-এ merge করতে হবে আর তার head return করতে হবে।

উদাহরণ

list1: 1 -> 4 -> 5
list2: 1 -> 3 -> 4
list3: 2 -> 6
ফল  : 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Input ও output¶

উদাহরণ

Input : [[1,4,5], [1,3,4], [2,6]]   -> Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Edge 1 (খালি লিস্টের list):  []          -> Output: None
Edge 2 (একটাই খালি list):    [[]]        -> Output: None
Edge 3 (কিছু খালি, কিছু না):  [[], [1]]   -> Output: 1

চেনা উদাহরণে বোঝা¶

k-টা কাউন্টারে আলাদা আলাদা sorted লাইন। তুমি একটা মিলিত sorted লাইন বানাচ্ছ। প্রতিবার প্রতিটা কাউন্টারের সামনের জন-দের মধ্যে সবচেয়ে কম টোকেন-নম্বরওয়ালাকে ডাকছ। সব কাউন্টারের সামনের জনকে বারবার চোখে চোখে তুলনা না করে, একটা "সবচেয়ে ছোট আগে" যন্ত্র (heap) রাখলে কাজটা দ্রুত হয়।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত্তি সরাসরি problem 2 ([002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)) — দুটো sorted list merge। সেখানে আমরা প্রতিবার দুই মাথার ছোটটা তুলতাম। এখানে দুইয়ের বদলে k-টা মাথা; তাই "সবচেয়ে ছোট মাথা" দ্রুত বের করতে দরকার একটা heap। এটাই heap data structure-এর প্রথম দরকারি ঝলক (preview)।

ভেতরের যুক্তি¶

লুকানো logic একই invariant, scale করা: যেহেতু প্রতিটা list sorted, সব list-এর মাথাগুলোর মধ্যে সবচেয়ে ছোটটাই পুরো অবশিষ্ট সবকিছুর মধ্যে ক্ষুদ্রতম — সেটাই পরের output node। শুধু k-টা মাথার মধ্যে min বারবার বের করা দরকার, আর min-heap সেটা O(log k)-তে দেয়। তাই N node-এ মোট O(N log k)।

কী দিয়ে তথ্য রাখব¶

একটা min-heap (Python-এ heapq) — যাতে যেকোনো মুহূর্তে k-টা list-এর মাথার মধ্যে সবচেয়ে ছোটটা O(log k)-তে তোলা যায়। সাথে merge-এর জন্য চেনা dummy head + tail।

এটি কেন উপযুক্ত¶

k-টা মাথা থেকে প্রতিবার min খুঁজতে সরল scan লাগত O(k); N বার করলে O(N·k)। min-heap সেই min-তোলা ও নতুন element ঢোকানো দুটোই O(log k)-তে করে। তাই heap ঠিক সেই operation-টা সস্তা করে যেটা ছাড়া সমাধান ধীর হতো — k বড় হলে এই পার্থক্য বিশাল।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

সরল চিন্তা: সব list-এর সব value একটা array-তে ঢালো, array-টা sort করো, তারপর sorted value দিয়ে একটা নতুন list বানাও।

উদাহরণ

[1,4,5]+[1,3,4]+[2,6] = [1,4,5,1,3,4,2,6]
sort -> [1,1,2,3,4,4,5,6] -> নতুন list

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা list already sorted — সেই তথ্য ফেলে দিয়ে N-টা element আবার সম্পূর্ণ sort করা মানে O(N log N), যেখানে N = সব node মিলিয়ে। heap ব্যবহার করলে প্রতি pop/push O(log k) (k = list সংখ্যা, সাধারণত N-এর চেয়ে অনেক ছোট), তাই O(N log k) — কম। তাছাড়া array + নতুন node-এ O(N) extra space।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: পরের output node সবসময় k-টা list-এর বর্তমান মাথাগুলোর মধ্যে সবচেয়ে ছোটটা। তাই পুরো খোঁজাখুঁজি নয় — শুধু একটা ছোট "min যন্ত্র"-এ k-টা মাথা রেখে বারবার ক্ষুদ্রতম তুলে নিলেই হয়, আর তোলা node-এর পরেরটা যন্ত্রে ঢুকিয়ে দিলেই হয়।

আরও কম কাজে সমাধান¶

শুরুতে প্রতিটা non-empty list-এর মাথা heap-এ ঢোকাও। তারপর বারবার: heap থেকে সবচেয়ে ছোট node তোলো, সেটা ফল-list-এর tail-এ জোড়ো, আর তার next (থাকলে) heap-এ push করো। heap খালি হলে শেষ। সমান value-তে tie ভাঙতে tuple-এ list index i রাখো, যাতে ListNode object তুলনা করতে না হয়।

ভাবনার পরিবর্তন¶

মোচড়: "দুই list merge"-কে k-তে বাড়াতে গিয়ে nested merge না ভেবে ভাবো — "প্রতিবার শুধু সবচেয়ে ছোট মাথা চাই; এটা তো একটা min-priority-queue-র কাজ।" দুই মাথার তুলনা → k মাথার min, আর min-এর জন্য heap — এই এক লাফেই brute force থেকে optimal-এ।

ছবিতে বোঝা¶

Input lists: [1,4,5], [1,3,4], [2,6]। Heap-এর প্রতিটি pair (value,list ID); table-এ heap-এর members পড়ার সুবিধায় sorted, internal heap array নয়।

ধাপ	pop	নতুন push	output	heap members
1	(1,L1)	(4,L1)	`[1]`	`(1,L2), (2,L3), (4,L1)`
2	(1,L2)	(3,L2)	`[1, 1]`	`(2,L3), (3,L2), (4,L1)`
3	(2,L3)	(6,L3)	`[1, 1, 2]`	`(3,L2), (4,L1), (6,L3)`
4	(3,L2)	(4,L2)	`[1, 1, 2, 3]`	`(4,L1), (4,L2), (6,L3)`
5	(4,L1)	(5,L1)	`[1, 1, 2, 3, 4]`	`(4,L2), (5,L1), (6,L3)`
6	(4,L2)	—	`[1, 1, 2, 3, 4, 4]`	`(5,L1), (6,L3)`
7	(5,L1)	—	`[1, 1, 2, 3, 4, 4, 5]`	`(6,L3)`
8	(6,L3)	—	`[1, 1, 2, 3, 4, 4, 5, 6]`	`empty`

ছোট input-এ ধাপে ধাপে¶

Input [[1,4],[2]]:

push মাথা: heap = {(1,0,n1), (2,1,n2)} (n1 = list0-এর 1, n2 = list1-এর 2)।
pop (1,0,n1) → out 1; n1.next = 4 push → heap = {(2,1,n2),(4,0,n4)}।
pop (2,1,n2) → out 1 2; n2.next = None, push নয় → heap = {(4,0,n4)}।
pop (4,0,n4) → out 1 2 4; n4.next = None → heap = {}।
heap খালি → শেষ। ফল 1 -> 2 -> 4।

কোড ও ব্যাখ্যা¶

Python¶

Python

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    heap = []
    # প্রতিটা non-empty list-এর মাথা push; i = tie ভাঙার জন্য list index
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()      # dummy head — head-এর special case এড়াতে
    tail = dummy
    while heap:
        val, i, node = heapq.heappop(heap)   # সবচেয়ে ছোট মাথা
        tail.next = node
        tail = tail.next
        if node.next:                        # তোলা node-এর পরেরটা heap-এ
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# ---- helpers (test-এর জন্য) ----
def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.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([])])) == []
assert to_list(merge_k_lists([build([]), build([1])])) == [1]
assert to_list(merge_k_lists([build([2, 2]), build([2])])) == [2, 2, 2]   # tie ভাঙা
print("সব test pass!")

কোডের প্রতিটি অংশ¶

import heapq — Python-এর min-heap (priority queue)।
প্রথম loop — প্রতিটা list-এর মাথা (val, i, node) রূপে push; খালি list বাদ।
(node.val, i, node) — heap val দিয়ে sort করে; সমান val-এ i (list index) tie ভাঙে, যাতে ListNode তুলনা করতে না হয় (object তুলনায় error)।
heapq.heappop(heap) — বর্তমান k মাথার মধ্যে সবচেয়ে ছোটটা O(log k)-তে।
tail.next = node; tail = tail.next — তোলা node ফল-list-এ জোড়ো।
if node.next: heappush(...) — তোলা node-এর পরের node heap-এ ঢোকাও, যাতে সেই list এগোয়।
return dummy.next — আসল head।

Output মিলিয়ে দেখা¶

[[1,4,5],[1,3,4],[2,6]]: শুরুতে heap-এ তিন মাথা (1,1,2)। বারবার ছোটটা তুলে আর পরেরটা push করে output দাঁড়ায় 1 1 2 3 4 4 5 6 → [1,1,2,3,4,4,5,6] — assert pass। খালি, এক-খালি, মিশ্র, সমান-value (tie) — সব pass; শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(N log k) — N = সব list মিলিয়ে মোট node; প্রতিটা node একবার push + একবার pop, প্রতিটা heap operation O(log k) (heap-এ সর্বোচ্চ k element)।

অতিরিক্ত জায়গা¶

O(k) — heap-এ একসাথে সর্বোচ্চ k-টা node (প্রতি list থেকে একটা মাথা)। ফল-list পুরোনো node reuse করে, তাই বাড়তি নয়।

যে ভুলগুলো এড়াতে হবে¶

heap tuple-এ tie-breaker না দেওয়া ((val, node)) — সমান val-এ Python ListNode তুলনা করতে গিয়ে TypeError। তাই মাঝে i (বা একটা counter) রাখো।
শুরুতে খালি list push করা — node None হলে crash; তাই if node: চেক করো।
তোলা node-এর next push করতে ভুলে যাওয়া — তখন সেই list আর এগোয় না, output অসম্পূর্ণ।
lists খালি ([]) আলাদা না ভাবা — heap খালি থাকে, dummy.next = None ঠিকঠাক ফেরে (এই code-এ এমনিতেই সামলায়)।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: merge two sorted lists ([002-merge-two-sorted-lists.md](002-merge-two-sorted-lists.md)) — দুই মাথার ছোটটা তোলার idea k-তে বাড়ানো, min খুঁজতে heap যোগ করে। dummy head কৌশলও সেখান থেকেই।

পরের অনুশীলন¶

Merge Two Sorted Lists (এই problem-এর বীজ) — https://leetcode.com/problems/merge-two-sorted-lists/ (এই tracker-এর #2)
Kth Smallest Element in a Sorted Matrix (heap + k-way) — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
Find K Pairs with Smallest Sums — https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

কৌশলটি মনে রাখুন¶

k-way merge with a min-heap: k-টা sorted উৎস থেকে বারবার ক্ষুদ্রতম তুলতে heap ব্যবহার — N মোট element হলে O(N log k)। heap-এর প্রথম বড় ব্যবহার।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "k-টা sorted জিনিস merge? প্রতিবার সবচেয়ে ছোট মাথা চাই — min-heap-এ k মাথা রাখো, pop করো, পরেরটা push করো।" tuple-এ index রেখে tie ভাঙতে ভুলো না, নাহলে object তুলনায় crash।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।