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

Time Complexity: Merge K Sorted Lists Using Min Heap

O(n log k)

Understanding Time Complexity

We want to understand how the time needed to merge multiple sorted lists grows as the number of lists and their sizes increase.

Specifically, how does using a min heap help manage this merging efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public ListNode MergeKLists(ListNode[] lists) {
    var minHeap = new SortedSet<(int val, int idx, ListNode node)>();
    for (int i = 0; i < lists.Length; i++) {
        if (lists[i] != null) {
            minHeap.Add((lists[i].val, i, lists[i]));
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    while (minHeap.Count > 0) {
        var smallest = minHeap.Min;
        minHeap.Remove(smallest);
        current.next = smallest.node;
        current = current.next;
        if (smallest.node.next != null) {
            minHeap.Add((smallest.node.next.val, smallest.idx, smallest.node.next));
        }
    }
    return dummy.next;
}
    

This code merges k sorted linked lists into one sorted list using a min heap to always pick the smallest current node.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Removing the smallest node from the min heap and adding 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 pushed and popped from the min heap once. The heap size is at most k (number of lists).

Input Size (n)	Approx. Operations
10 nodes, 3 lists	About 10 insertions and removals from a heap of size ≤ 3
100 nodes, 5 lists	About 100 insertions and removals from a heap of size ≤ 5
1000 nodes, 10 lists	About 1000 insertions and removals from a heap of size ≤ 10

Pattern observation: Operations grow linearly with total nodes, but each heap operation depends on k, which is usually much smaller than n.

Final Time Complexity

Time Complexity: O(n log k)

This means the time grows mostly with the total number of nodes, multiplied by the cost of managing the heap of size 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 requires extra work managed by the heap, making it slower than just merging two lists.

Interview Connect

Understanding this time complexity helps you explain why using a min heap is efficient and expected when merging multiple sorted lists in real problems.

Self-Check

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

Practice

1. What is the main purpose of using a min heap when merging K sorted linked lists?

easy

A. To efficiently get the smallest current element among all lists

B. To store all elements in sorted order before merging

C. To reverse the order of elements in each list

D. To count the total number of elements in all lists

Solution

1. Step 1: Understand the role of min heap in merging

   A min heap helps quickly find the smallest element among multiple sorted lists without scanning all elements.

2. Step 2: Why min heap is chosen

   It maintains the smallest element at the top, so we can pick and remove it efficiently while merging.

3. Final Answer:

   To efficiently get the smallest current element among all lists -> Option A

4. Quick Check:

   Min heap = smallest element retrieval [OK]

Hint: Min heap always gives smallest element fast [OK]

Common Mistakes:

• Thinking min heap stores all elements sorted
• Confusing min heap with max heap
• Using min heap to count elements

2. Which of the following is the correct way to initialize a min heap in C# for merging K sorted lists?

easy

A. var minHeap = new List<int>();

B. var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();

C. var minHeap = new Queue<ListNode>();

D. var minHeap = new Stack<ListNode>();

Solution

1. Step 1: Identify data structure for min heap

   SortedSet with tuple (value, list index, node) can act as a min heap by sorting elements by value.

2. Step 2: Why other options are incorrect

   List, Queue, and Stack do not maintain sorted order automatically, so they can't serve as min heap.

3. Final Answer:

   var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>(); -> Option B

4. Quick Check:

   SortedSet = min heap structure [OK]

Hint: Use SortedSet with tuples for min heap in C# [OK]

Common Mistakes:

• Using List or Queue as min heap
• Not including value for sorting in tuple
• Confusing Stack with heap

3. What will be the output linked list after merging these 3 sorted lists using a min heap?

List 1: 1 -> 4 -> 5 -> null
List 2: 1 -> 3 -> 4 -> null
List 3: 2 -> 6 -> null

medium

A. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

B. 1 -> 3 -> 4 -> 1 -> 4 -> 5 -> 2 -> 6 -> null

C. 6 -> 5 -> 4 -> 4 -> 3 -> 2 -> 1 -> 1 -> null

D. 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

Solution

1. Step 1: Insert first nodes of all lists into min heap

   Insert 1 (List1), 1 (List2), 2 (List3) into min heap.

2. Step 2: Extract min and add next nodes

   Extract 1 (List1), add 4; extract 1 (List2), add 3; extract 2 (List3), add 6; continue extracting min and adding next nodes until all lists are merged.

3. Final Answer:

   1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null -> Option D

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Always pick smallest node from heap and add next from same list [OK]

Common Mistakes:

• Not adding next node after extracting min
• Merging lists without sorting
• Confusing order of nodes

4. Given the following code snippet for merging K sorted lists, what is the error?

var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();
foreach (var list in lists) {
  if (list != null) minHeap.Add((list.val, 0, list));
}
while (minHeap.Count > 0) {
  var min = minHeap.Min;
  minHeap.Remove(min);
  // Add min.node to result
  if (min.node.next != null) {
    minHeap.Add((min.node.next.val, min.listIndex + 1, min.node.next));
  }
}

medium

A. Incrementing listIndex incorrectly when adding next node

B. Not checking if list is null before adding to heap

C. Using SortedSet instead of PriorityQueue

D. Not removing min element from heap

Solution

1. Step 1: Understand listIndex usage

   listIndex should identify which list the node belongs to and remain constant for that list.

2. Step 2: Identify error in incrementing listIndex

   Incrementing listIndex by 1 when adding next node is wrong; it should stay the same to track correct list.

3. Final Answer:

   Incrementing listIndex incorrectly when adding next node -> Option A

4. Quick Check:

   listIndex must not change per node [OK]

Hint: Keep listIndex fixed per list, don't increment per node [OK]

Common Mistakes:

• Changing listIndex for next nodes
• Forgetting to remove min element
• Ignoring null checks

5. You have 4 sorted linked lists with lengths 2, 3, 4, and 5 respectively. Using a min heap, what is the time complexity to merge all lists into one sorted list?

hard

A. O(N + K), where N is total nodes and K is number of lists

B. O(N K), where N is total nodes and K is number of lists

C. O(N log K), where N is total nodes and K is number of lists

D. O(K log N), where N is total nodes and K is number of lists

Solution

1. Step 1: Calculate total nodes and understand K

   Total nodes N = 2 + 3 + 4 + 5 = 14, K = 4 lists.

2. Step 2: Analyze min heap operations

   Each node is pushed and popped once from min heap of size K, so operations take O(log K) each.

3. Step 3: Combine to get total complexity

   Total time = O(N log K) because each of N nodes involves heap operations.

4. Final Answer:

   O(N log K), where N is total nodes and K is number of lists -> Option C

5. Quick Check:

   Heap operations per node = log K [OK]

Hint: Merging K lists with heap = O(N log K) time [OK]

Common Mistakes:

• Assuming O(N K) instead of O(N log K)
• Ignoring heap operation cost
• Confusing N and K roles