Merge K Sorted Lists Using Min Heap in DSA Javascript - Time & Space Complexity

Time Complexity: Merge K Sorted Lists Using Min Heap

O(n log k)

Understanding Time Complexity

When merging multiple sorted lists, we want to know how the time needed grows as the number of lists and their sizes increase.

We ask: How does the merging time change when we have more lists or longer lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function mergeKLists(lists) {
  const minHeap = new MinHeap();
  for (const list of lists) {
    if (list) minHeap.insert(list);
  }
  const dummy = new ListNode(0);
  let current = dummy;
  while (!minHeap.isEmpty()) {
    const node = minHeap.extractMin();
    current.next = node;
    current = current.next;
    if (node.next) minHeap.insert(node.next);
  }
  return dummy.next;
}
    

This code merges k sorted linked lists by always picking the smallest current node using a min heap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Extracting the smallest node from the min heap and inserting the next node from that list.
• How many times: This happens once for every node across all lists, so total nodes n times.

How Execution Grows With Input

Each node is inserted and extracted from the heap, which takes time depending on the number of lists k.

Input Size (n)	Approx. Operations
10 nodes, 3 lists	About 10 insertions and 10 extractions, each costing log 3 steps
100 nodes, 5 lists	About 100 insertions and 100 extractions, each costing log 5 steps
1000 nodes, 10 lists	About 1000 insertions and 1000 extractions, each costing log 10 steps

Pattern observation: The total work grows roughly with the total number of nodes times the log of the number of lists.

Final Time Complexity

Time Complexity: O(n log k)

This means the time grows with the total number of nodes n multiplied by the logarithm of the number of lists k.

Common Mistake

[X] Wrong: "Merging k lists is just like merging two lists, so it takes O(n) time."

[OK] Correct: Merging k lists involves repeatedly choosing the smallest among k current nodes, which costs extra time. The heap helps manage this efficiently, but the log k factor matters.

Interview Connect

Understanding this complexity shows you can handle multiple sorted inputs efficiently, a common real-world task when combining data streams or search results.

Self-Check

"What if we used a simple array instead of a min heap to find the smallest node each time? How would the time complexity change?"