024 — Merge k Sorted Lists

Source

• Original source: Classic k-way merge interview problem
• Platform: LeetCode — https://leetcode.com/problems/merge-k-sorted-lists/
• 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)-তে তোলা), 04 linked lists (node-এর pointer ধরে output list গড়া), আর 03 merging (দুটো sorted ধারা মেশানোর ধারণাকে k-ধারায় তোলা)। তিন জোড়া লাগলেই O(N log k) merge।

1. Problem in simple words

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

lists = [ 1->4->5 ,  1->3->4 ,  2->6 ]
merge : 1->1->2->3->4->4->5->6

2. Which basic idea does this inherit from?

এই problem তিনটা আগের chapter-এর tool জোড়া দেয়:

• 08 heaps (../../08-heaps-and-priority-queues/) থেকে: k-টা list-এর বর্তমান মাথার মধ্যে সবচেয়ে ছোটটা প্রতিবার O(log k)-তে বের করা।
• 04 linked lists (../../04-linked-lists/) থেকে: node-এর next pointer ধরে এগোনো আর dummy head দিয়ে output list গড়া।
• 03 merging (../../03-searching-and-sorting/) থেকে: "দুটো 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 করা যায় (04 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-ই সবচেয়ে খাপ-খাওয়া জোড়া।

6. Real-life analogy

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

7. Visual explanation

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    ...->4             5 (list0)
 6    {5,4,6}          4    ...->4->4          (list1 শেষ)
 7    {5,6}            5    ...->5             (list0 শেষ)
 8    {6}              6    ...->6             (list2 শেষ)
ফল:  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 case 1 (পুরো খালি): []        -> []        # কোনো list নেই
Edge case 2 (খালি list সহ): [[],[1]] -> [1]      # খালি list বাদ পড়ে
Edge case 3 (একটা list): [[2,7,9]]  -> [2,7,9]

9. Brute force thinking

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

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 কাজে লাগিয়ে।

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

15. Python solution

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()                     # 04 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 (04 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 (03 merging-এর "ধারা এগিয়ে নাও")।
• return dummy.next — merged sorted list-এর head।

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

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) করো।

21. Which basic problem this inherits from

ভিত্তি: min-heap দিয়ে বারবার minimum তোলা (08 heaps-এর ../../08-heaps-and-priority-queues/) + linked list pointer আর dummy-head দিয়ে list গড়া (04-এর ../../04-linked-lists/) + দুটো sorted list merge করার ধারণা (03-এর ../../03-searching-and-sorting/)। দুই-list merge cold অবস্থায় জানা থাকলে heap দিয়ে এটাই k-way-তে বাড়ে। (../hard-patterns.md-এর combo 3-এর "always need the smallest frontier" instinct।)

22. Similar harder problems

• Merge Two Sorted Lists (এই problem-এর two-way ভিত্তি; heap ছাড়া) — https://leetcode.com/problems/merge-two-sorted-lists/
• Smallest Range Covering Elements from K Lists (k frontier-এ heap, কিন্তু range track) — https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/
• Find K Pairs with Smallest Sums (heap over frontier of pairs) — https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

23. Pattern learned

Heap over k frontiers: যখন k-টা sorted ধারা মেশাতে হয়, প্রতিটার বর্তমান মাথা একটা min-heap-এ রাখো; বারবার সবচেয়ে ছোটটা pop করে output-এ দাও আর সেই ধারার পরের element push করো। দুই-way merge-এর k-way generalization — "merge / pick smallest across k sorted streams" problem-এর canonical রূপ।

24. Final summary

ভবিষ্যতের আমাকে: "k-টা sorted জিনিস মেশাও" বা "k frontier-এর মধ্যে বারবার সবচেয়ে ছোট" শুনলেই min-heap মনে করবে। প্রতিটা list-এর মাথা heap-এ ঢালো, pop করে output-এ দাও, popped-এর next push করো — heap সবসময় ≤ k, তাই O(N log k)। heap-এ value-র সাথে tie-breaker counter দাও যাতে node compare না হয়, আর dummy head দিয়ে output গড়ো। এটা heaps + linked lists + merging-এর পরিষ্কার মেলবন্ধন।

---

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