কনটেন্টে যান

024 — Merge k Sorted Lists

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • 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)-তে তোলা), 03 linked lists (node-এর pointer ধরে output list গড়া), আর two-way merging (দুটো sorted ধারা মেশানোর ধারণাকে k-ধারায় তোলা)। তিন জোড়া লাগলেই O(N log k) merge।

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

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

তোমাকে দেওয়া আছে 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

Input ও 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]

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

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

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

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

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

  • 08 heaps (../../08-heap-priority-queue/) থেকে: k-টা list-এর বর্তমান মাথার মধ্যে সবচেয়ে ছোটটা প্রতিবার O(log k)-তে বের করা।
  • 03 linked lists (../../03-linked-list/) থেকে: node-এর next pointer ধরে এগোনো আর dummy head দিয়ে output list গড়া।
  • two-way merging (পূর্বশর্ত) থেকে: "দুটো sorted ধারার মাথা তুলনা করে ছোটটা নাও" — এই two-way merge-এর ধারণা k-way-তে generalize করা।

একা merge দেয় "ছোটটা আগে" নিয়ম; একা heap দেয় k-এর মধ্যে minimum fast পাওয়া; linked list pointer দেয় output গাঁথা। তিন মিলে O(N log k)।

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

লুকানো 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-এ নামায়।

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

দরকার: (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 না করতে)।

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

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-ই সবচেয়ে খাপ-খাওয়া জোড়া।

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

প্রথম সরল উপায়

প্রথম সরল চিন্তা: সব 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 গড়ো

কোথায় বেশি কাজ হচ্ছে

সব 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 নেয়।)

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

মূল observation: পরের output element সবসময় k-টা list-এর মাথার মধ্যেই লুকিয়ে — গোটা data নয়, শুধু k-টা frontier দেখলেই চলে। তাই পুরো N-কে বারবার না দেখে, প্রতি step-এ শুধু k-টা candidate-এর minimum বের করি; একটা নিলে সেই list-এর পরের node candidate হয়। min-heap এই "k-এর minimum, বারবার" কাজটার জন্যই তৈরি।

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

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

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

মোচড়: "সবকিছু এক জায়গায় এনে sort করব" ভাবা ছাড়ো। ভাবো "প্রতি মুহূর্তে শুধু k-টা মাথা দেখলেই পরের element নিশ্চিত — দরকার শুধু k-এর minimum বারবার।" বিশাল sort একটা ছোট k-size heap-এর streaming pop-এ পরিণত হয়, sortedness কাজে লাগিয়ে।

ছবিতে বোঝা

উদাহরণ
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-এ ধাপে ধাপে

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

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

Python

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

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

  • 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 মিলিয়ে দেখা

তিন 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!।

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

সময়

O(N log k) — N = মোট node; প্রতিটা node ঠিক একবার heap-এ push আর একবার pop, heap-এ সর্বদা ≤ k element তাই প্রতি op O(log k)।

অতিরিক্ত জায়গা

O(k) — heap বড়জোর k element ধরে (প্রতিটা list থেকে একটা মাথা); output list reuse করছে input node, তাই extra node তৈরি হয় না।

যে ভুলগুলো এড়াতে হবে

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

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

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

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

পরের অনুশীলন

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

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 রূপ।

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

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