019 — Merge k Sorted Lists¶

Source¶

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

1. Problem in simple words¶

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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

heap-এ রাখি (node.val, i, node); i = list index (সমান val-এ tie ভাঙতে):

শুরু — প্রতিটা list-এর মাথা push:
  heap = {(1, l1), (1, l2), (2, l3)}

pop (1, l1) → out: 1 ; l1.next=4 push  → heap {(1,l2),(2,l3),(4,l1)}
pop (1, l2) → out: 1 1 ; l2.next=3 push → heap {(2,l3),(3,l2),(4,l1)}
pop (2, l3) → out: 1 1 2 ; l3.next=6 push → heap {(3,l2),(4,l1),(6,l3)}
pop (3, l2) → 1 1 2 3 ; push 4(l2)
pop (4, l1) → 1 1 2 3 4 ; push 5(l1)
... চলতে চলতে → 1 1 2 3 4 4 5 6

8. Example input and 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

9. Brute force thinking¶

সরল চিন্তা: সব 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

10. Why brute force is slow¶

প্রতিটা 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।

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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।

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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।

17. Output walkthrough¶

[[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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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-এ এমনিতেই সামলায়)।

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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/

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।