Solusi Leetcode - Merge k Sorted Lists

Merge k sorted list secara berurutan bakal memproses node dari list-list sebelumnya berulang kali. Dengan jumlah list sampai 10.000, perbandingan yang berulang itu bisa mendominasi kerjanya.

Min heap dan divide and conquer mengurangi perbandingan node yang berulang di versi sequential.

Memahami Soalnya

Kita dikasih array berisi k linked list, dan setiap list udah terurut secara ascending. Tugas kita adalah merge semuanya jadi satu linked list yang terurut.

Ini batasannya:

• k == lists.length
• 0 <= k <= 10^4 (sampai 10.000 list!)
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] terurut secara ascending
• Jumlah total lists[i].length nggak akan melebihi 10^4

Contoh 1:

• Input: lists = [[1,4,5],[1,3,4],[2,6]]
• Output: [1,1,2,3,4,4,5,6]

Contoh 2:

• Input: lists = []
• Output: []

Contoh 3:

• Input: lists = [[]]
• Output: []

Pendekatan Pertama Saya: Merge Satu per Satu

Pikiran pertama saya simpel: ambil list pertama, merge dengan list kedua, lalu merge hasilnya dengan list ketiga, dan seterusnya.

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  
  // Merge two sorted lists
  function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (l1 && l2) {
      if (l1.val < l2.val) {
        current.next = l1;
        l1 = l1.next;
      } else {
        current.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }
    
    current.next = l1 || l2;
    return dummy.next;
  }
  
  // Merge lists one by one
  let result = lists[0];
  for (let i = 1; i < lists.length; i++) {
    result = mergeTwoLists(result, lists[i]);
  }
  
  return result;
}

Cara ini jalan, tapi nggak efisien. Dengan k list yang masing-masing berisi n node:

Time Complexity: O(k² × n)

• Merge pertama: n + n = 2n
• Merge kedua: 2n + n = 3n
• Merge ketiga: 3n + n = 4n
• ...dan seterusnya
• Total: n + 2n + 3n + ... + kn = n(1 + 2 + 3 + ... + k) = O(k² × n)

Scan yang berulang ini mahal kalau k = 10.000.

Insight dari Divide and Conquer

Hitungan kompleksitas tadi menunjukkan ke saya seberapa mahal perbandingan node yang berulang. Jadi saya merge list secara berpasangan, lalu merge hasilnya secara berpasangan juga.

Setiap ronde mengurangi jumlah list:

• Ronde 1: Merge list[0] dengan list[1], list[2] dengan list[3], dan seterusnya.
• Ronde 2: Merge hasil dari ronde 1
• Lanjutkan sampai tersisa satu list

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  
  function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while (l1 && l2) {
      if (l1.val < l2.val) {
        current.next = l1;
        l1 = l1.next;
      } else {
        current.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }
    
    current.next = l1 || l2;
    return dummy.next;
  }
  
  // Divide and conquer
  while (lists.length > 1) {
    const mergedLists = [];
    
    for (let i = 0; i < lists.length; i += 2) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null;
      mergedLists.push(mergeTwoLists(l1, l2));
    }
    
    lists = mergedLists;
  }
  
  return lists[0];
}

Time Complexity: O(N log k)

• Ada log k level (setiap level membagi dua jumlah list)
• Di setiap level, kita memproses total N node
• Total: O(N log k)

Space Complexity: O(k)

Setiap ronde membuat array mergedLists yang berisi head dari list. Ronde pertama menyimpan sampai ceil(k / 2) head. Kode ini memakai ulang node dari input, tapi array tambahannya tetap butuh O(k) space.

Untuk lists = [[1,4,5],[1,3,4],[2,6]], proses merge-nya berjalan seperti ini:

Ronde 1: Merge berpasangan

• Merge [1,4,5] dan [1,3,4] → [1,1,3,4,4,5]
• Merge [2,6] dan null → [2,6]
• Setelah ronde 1: [[1,1,3,4,4,5], [2,6]]

Ronde 2: Merge berpasangan

• Merge [1,1,3,4,4,5] dan [2,6] → [1,1,2,3,4,4,5,6]
• Setelah ronde 2: [[1,1,2,3,4,4,5,6]]

Tersisa satu list hasil merge.

Pendekatan min heap

Opsi kedua adalah min heap. Di titik mana pun, kita cuma butuh nilai terkecil di antara head saat ini dari k list.

Idenya:

1. Masukkan node pertama dari setiap list ke min heap
2. Ambil nilai minimum, yang jadi node berikutnya
3. Kalau node itu punya node berikutnya, tambahkan ke heap
4. Ulangi sampai heap kosong

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  
  // Min-heap implementation using array
  class MinHeap {
    constructor() {
      this.heap = [];
    }
    
    push(node) {
      this.heap.push(node);
      this.bubbleUp(this.heap.length - 1);
    }
    
    pop() {
      if (this.heap.length === 0) return null;
      if (this.heap.length === 1) return this.heap.pop();
      
      const min = this.heap[0];
      this.heap[0] = this.heap.pop();
      this.bubbleDown(0);
      return min;
    }
    
    bubbleUp(index) {
      while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[index].val >= this.heap[parentIndex].val) break;
        
        [this.heap[index], this.heap[parentIndex]] = 
          [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      }
    }
    
    bubbleDown(index) {
      while (true) {
        let smallest = index;
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        
        if (leftChild < this.heap.length && 
            this.heap[leftChild].val < this.heap[smallest].val) {
          smallest = leftChild;
        }
        
        if (rightChild < this.heap.length && 
            this.heap[rightChild].val < this.heap[smallest].val) {
          smallest = rightChild;
        }
        
        if (smallest === index) break;
        
        [this.heap[index], this.heap[smallest]] = 
          [this.heap[smallest], this.heap[index]];
        index = smallest;
      }
    }
    
    isEmpty() {
      return this.heap.length === 0;
    }
  }
  
  const heap = new MinHeap();
  
  // Add first node from each list to heap
  for (const list of lists) {
    if (list) heap.push(list);
  }
  
  const dummy = new ListNode(0);
  let current = dummy;
  
  // Extract min and add next nodes
  while (!heap.isEmpty()) {
    const node = heap.pop();
    current.next = node;
    current = current.next;
    
    if (node.next) {
      heap.push(node.next);
    }
  }
  
  return dummy.next;
}

Time Complexity: O(N log k) dengan N adalah jumlah total node

• Setiap node dari N node dimasukkan ke heap dan diambil dari heap sekali
• Setiap operasi heap butuh O(log k) time
• Total: O(N log k)

Space Complexity: O(k) untuk heap-nya

Untuk k = 10.000 dan N = 10.000, heap-nya melakukan kerja sebesar O(N log k), bukan O(kN) seperti di metode sequential.

Membandingkan Kedua Pendekatan

Kedua metode butuh kerja merge sebesar O(N log k) kalau k minimal dua. Keduanya juga memeriksa k head dari list input. Batas yang juga mencakup list kosong dan k = 1 adalah O(k + N log(k + 1)).

Saya lebih suka divide and conquer karena:

• Memakai helper merge berpasangan tanpa operasi heap
• Lebih simpel untuk dipahami dan diimplementasikan
• Kamu mungkin udah tahu cara merge dua list

Tapi min heap bagus kalau:

• Kamu udah nyaman dengan struktur data heap
• Kamu mau memproses node secara bertahap
• Space untuk k node masih bisa diterima

Jebakan yang Sering Muncul

Waktu mengimplementasikan solusi-solusi ini, hati-hati dengan:

1. Pengecekan null: Selalu tangani list kosong, list null, dan list yang isinya cuma list kosong.

2. Edge case:

   • Array input kosong: lists = []
   • Array dengan satu list kosong: lists = [[]]
   • Array dengan campuran list kosong dan list yang nggak kosong

3. Implementasi heap: Kalau bikin heap sendiri, pastikan perbandingannya benar (min heap pakai < bukan >).

4. Off by one error: Di divide and conquer, waktu memasangkan list, tangani jumlah list yang ganjil dengan benar.

5. Dummy node: Memakai dummy node bikin kode jauh lebih bersih. Jangan lupa return dummy.next, bukan dummy.

Memilih strategi merge

• Merge sequential yang naif itu O(k² × n), yang nggak cocok untuk k yang besar
• Min heap dan divide and conquer sama-sama mencapai O(N log k)
• Kedua implementasi memakai O(k) auxiliary space: heap menyimpan node, dan divide and conquer menyimpan head dari list
• Pola divide and conquer juga muncul di merge sort, dan batasan soalnya yang seharusnya menentukan pilihan