LeetCode Grinding
Algorithms4 menit baca

Solusi Leetcode - Merge k Sorted Lists

Membandingkan metode sequential, pairwise, dan heap untuk merge beberapa linked list yang udah terurut.

Di artikel ini 6 bagian

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: []

Menggabungkan satu list setiap langkah

Gabungkan dua list pertama, lalu gabungkan hasilnya dengan list ketiga, dan lanjutkan. Cara ini memakai ulang function merge dua list, tapi hasil gabungannya ditelusuri berkali-kali.

javascript
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.

Menggabungkan secara berpasangan

Memasangkan list menghindari penggabungan hasil yang makin besar dengan satu list kecil secara berulang. Setiap ronde menggabungkan hasil pasangan sebelumnya.

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
javascript
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
javascript
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)).

PendekatanTime ComplexitySpace ComplexityKelebihanKekurangan
Divide and conquerO(N log k)O(k)Merge berpasanganButuh array berisi head dari list
Min-heapO(N log k)O(k)Pemrosesan bertahapLebih kompleks, O(k) space

Aku lebih memilih divide and conquer di sini karena bisa memakai ulang helper merge berpasangan tanpa implementasi heap terpisah.

Min heap berguna kalau output perlu dihasilkan secara bertahap. Heap cuma menyimpan head saat ini dari setiap list.

Jebakan yang Sering Muncul

  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.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan