Merge K Sorted Lists Using Min Heap in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the min heap for merging sorted lists.

DSA C#

var minHeap = new SortedSet<(int val, int listIndex, int elementIndex)>[1];

Drag options to blanks, or click blank then click option'

A()

B[]

C{}

D<>

Attempts:

3 left

💡 Hint

Common Mistakes

Using square brackets [] instead of parentheses () to initialize the SortedSet.

Using curly braces {} which is invalid here.

The min heap is initialized as an empty SortedSet with parentheses ().

2fill in blank

medium

Complete the code to add the first element of each list to the min heap.

DSA C#

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

while (minHeap.Count > 0) {
    var current = minHeap.Min;
    minHeap.Remove(current);
    result.Add(current.val);
    int nextIndex = current.elementIndex + 1;
    if (nextIndex < lists[current.listIndex].Count) {
        minHeap.Add([1]);
    }
}

Drag options to blanks, or click blank then click option'

A(current.val, current.listIndex, nextIndex)

B(lists[current.listIndex][nextIndex], current.listIndex, nextIndex)

C(lists[current.listIndex][current.elementIndex], current.listIndex, nextIndex)

D(lists[current.listIndex][nextIndex], nextIndex, current.listIndex)

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping listIndex and elementIndex in the tuple.

Using current.val instead of the next element's value.

We add the next element from the same list to the min heap with its value, list index, and element index.

3fill in blank

hard

Fix the error in the comparison logic for the SortedSet to maintain min heap order.

DSA C#

var minHeap = new SortedSet<(int val, int listIndex, int elementIndex)>(Comparer<(int, int, int)>.Create((a, b) => {
    if (a.val != b.val) return a.val - b.val;
    if (a.listIndex != b.listIndex) return a.listIndex - b.listIndex;
    return [1];
}));

Drag options to blanks, or click blank then click option'

Aa.listIndex - b.listIndex

Bb.elementIndex - a.elementIndex

Ca.elementIndex - b.elementIndex

Db.listIndex - a.listIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Reversing the subtraction causing descending order.

Comparing listIndex again instead of elementIndex.

To maintain consistent ordering, compare elementIndex ascending as the last tie-breaker.

4fill in blank

hard

Fill both blanks to complete the loop that merges k sorted lists using the min heap.

DSA C#

while (minHeap.Count > 0) {
    var current = minHeap.Min;
    minHeap.Remove(current);
    result.Add([1]);
    int nextIndex = current.elementIndex + 1;
    if (nextIndex < lists[[2]].Count) {
        minHeap.Add((lists[current.listIndex][nextIndex], current.listIndex, nextIndex));
    }
}

Drag options to blanks, or click blank then click option'

Acurrent.val

Bcurrent.listIndex

Ccurrent.elementIndex

DnextIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Adding current.elementIndex instead of current.val to result.

Using nextIndex instead of current.listIndex to access lists.

Add the current value to result and check the next element in the same list using current.listIndex.

5fill in blank

hard

Fill all three blanks to complete the method that merges k sorted lists using a min heap.

DSA C#

public List<int> MergeKSortedLists(List<int>[] lists) {
    var result = new List<int>();
    var minHeap = new SortedSet<(int val, int listIndex, int elementIndex)>(Comparer<(int, int, int)>.Create((a, b) => {
        if (a.val != b.val) return a.val - b.val;
        if (a.listIndex != b.listIndex) return a.listIndex - b.listIndex;
        return a.elementIndex - b.elementIndex;
    }));

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

    while (minHeap.Count > 0) {
        var current = minHeap.Min;
        minHeap.Remove(current);
        result.Add([1]);
        int nextIndex = current.elementIndex + 1;
        if (nextIndex < lists[[2]].Count) {
            minHeap.Add((lists[[3]][nextIndex], current.listIndex, nextIndex));
        }
    }

    return result;
}

Drag options to blanks, or click blank then click option'

Acurrent.val

Bcurrent.listIndex

Ccurrent.elementIndex

DnextIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Using nextIndex instead of current.listIndex to access lists.

Adding elementIndex instead of val to the result.

Add current.val to result, use current.listIndex to check the next element and add it to the min heap.

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