Merge K Sorted arrays

Question

Given three sorted linked lists, merge them into a single sorted result.

Codemia · Accepted Answer

To merge K sorted linked lists, we can recognize that this problem aligns with the **merge process of the merge sort algorithm**. Given that each linked list is already sorted, we can efficiently merge them using a priority queue (min-heap). This allows us to always extract the smallest element across the lists in logarithmic time, which is optimal for this scenario. The reason a priority queue fits here is that we need to repeatedly retrieve the minimum element among the heads of the linked lists, ensuring that the merged list remains sorted.

1. **Initialization**: Create a min-heap (priority queue) to hold the heads of the linked lists. 
2. **Heap Population**: Insert the head of each linked list into the min-heap. 
3. **Merge Process**: 
   - While the min-heap is not empty: 
     - Extract the smallest element (the root of the min-heap) and append it to the result list. 
     - If the extracted element has a next node, insert that next node into the min-heap. 
4. **Return Result**: Convert the result list from a linked list to an array or return it as needed.

**Example**: Given linked lists: 
- List1: 1 -> 4 -> 5 
- List2: 1 -> 3 -> 4 
- List3: 2 -> 6 
The min-heap starts with [1, 1, 2]. The extraction order will yield: 1, 1, 2, 3, 4, 4, 5, 6.

```python
import heapq
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    min_heap = []
    # Populate the heap with the head nodes of each list
    for node in lists:
        if node:
            heapq.heappush(min_heap, (node.val, node))

dummy = ListNode(0)
    current = dummy

while min_heap:
        val, node = heapq.heappop(min_heap)
        current.next = ListNode(val)
        current = current.next
        # If there's a next node, push it onto the heap
        if node.next:
            heapq.heappush(min_heap, (node.next.val, node.next))

return dummy.next
```

The time complexity of this approach is **O(N log K)**, where N is the total number of nodes across all linked lists, and K is the number of linked lists. This is because we perform a push and pop operation on the heap for each node, and each operation takes O(log K) time. The space complexity is **O(K)** due to the storage of the heap which holds at most K nodes (one from each list at any time).

1. **Empty Input**: If the input list of linked lists is empty (i.e., `lists = []`), the function should return `None` or an empty list.  
2. **All Lists Empty**: If all linked lists are empty (i.e., `lists = [None, None]`), it should also return `None`.  
3. **Single List**: If there is only one linked list, the output should be the same as the input linked list.  
4. **Different Lengths**: Ensure that the solution handles linked lists of varying lengths correctly, merging them into a single sorted list.

Merge K Sorted arrays

Dropbox

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Dropbox Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string