Merge K Sorted Lists Using Min Heap in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging 3 sorted linked lists using min heap

What is the printed state of the merged linked list after running the following C# code that merges 3 sorted linked lists using a min heap?

DSA C#

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        var minHeap = new SortedSet<(int val, int idx, ListNode node)>(Comparer<(int, int, ListNode)>.Create((a, b) => {
            int cmp = a.val.CompareTo(b.val);
            if (cmp == 0) return a.idx.CompareTo(b.idx);
            return cmp;
        }));

        for (int i = 0; i < lists.Length; i++) {
            if (lists[i] != null) {
                minHeap.Add((lists[i].val, i, lists[i]));
            }
        }

        ListNode dummy = new ListNode();
        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;
    }

    public static void PrintList(ListNode head) {
        while (head != null) {
            Console.Write(head.val);
            if (head.next != null) Console.Write(" -> ");
            head = head.next;
        }
        Console.WriteLine(" -> null");
    }

    public static void Main() {
        ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode l3 = new ListNode(2, new ListNode(6));

        Solution sol = new Solution();
        ListNode merged = sol.MergeKLists(new ListNode[] { l1, l2, l3 });
        PrintList(merged);
    }
}

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

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

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

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

💡 Hint

Think about how the min heap always picks the smallest current node from all lists.

The min heap picks the smallest node among the heads of all lists repeatedly. The merged list contains all nodes in sorted order from all three lists combined.

🧠 Conceptual

intermediate

Why use a min heap to merge K sorted lists?

Which of the following best explains why a min heap is used to merge K sorted linked lists efficiently?

A It sorts each individual list before merging.

B It stores all nodes in memory at once, making traversal faster.

C It allows quick access to the smallest current node among all lists, reducing overall time complexity.

D It reverses the order of nodes to merge lists from largest to smallest.

💡 Hint

Think about how to always pick the smallest element efficiently.

A min heap keeps track of the smallest elements from each list, allowing efficient extraction of the smallest node at each step, which leads to an overall time complexity of O(N log K) where N is total nodes and K is number of lists.

🔧 Debug

advanced

Identify the error in this min heap merge implementation

What error will the following code produce when merging K sorted lists using a min heap in C#?

DSA C#

var minHeap = new SortedSet<(int val, ListNode node)>(Comparer<(int, ListNode)>.Create((a, b) => a.val.CompareTo(b.val)));

for (int i = 0; i < lists.Length; i++) {
    if (lists[i] != null) {
        minHeap.Add((lists[i].val, lists[i]));
    }
}

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.node.next));
    }
}

A Runtime error due to duplicate keys in SortedSet causing exception

B Syntax error because of missing semicolons

C No error, code runs correctly

D Logical error: merged list will be reversed

💡 Hint

Consider how SortedSet compares tuples with same values but different nodes.

SortedSet requires unique keys. When two nodes have the same value, the comparer returns 0, causing SortedSet to treat them as duplicates and throw an exception.

❓ Predict Output

advanced

Output after merging empty and non-empty lists

What is the output of merging the following 3 lists using min heap? Lists: [] (empty), [2 -> 3 -> 7], [1 -> 4]

DSA C#

ListNode l1 = null;
ListNode l2 = new ListNode(2, new ListNode(3, new ListNode(7)));
ListNode l3 = new ListNode(1, new ListNode(4));

Solution sol = new Solution();
ListNode merged = sol.MergeKLists(new ListNode[] { l1, l2, l3 });
Solution.PrintList(merged);

A 1 -> 4 -> 2 -> 3 -> 7 -> null

B 2 -> 3 -> 7 -> 1 -> 4 -> null

C null

D 1 -> 2 -> 3 -> 4 -> 7 -> null

💡 Hint

Empty lists do not affect the merged output.

The merged list contains all nodes from the non-empty lists in sorted order: 1, 2, 3, 4, 7.

🧠 Conceptual

expert

Time complexity of merging K sorted lists using a min heap

What is the time complexity of merging K sorted linked lists with a total of N nodes using a min heap?

A O(N log K)

B O(K log N)

C O(N K)

D O(N + K)

💡 Hint

Consider how many times you insert and remove nodes from the heap and the heap size.

Each of the N nodes is inserted and removed from the min heap once. The heap size is at most K, so each operation takes O(log K). Total time is O(N log K).

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