Merge K Sorted arrays

Question

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

Codemia · Accepted Answer

To tackle the problem of merging three sorted linked lists, we can recognize that the appropriate pattern to apply here is the **two pointers technique**. This is because we have three separate sorted sequences, and our goal is to efficiently combine them into a single sorted sequence. Each linked list acts like a stream of sorted data, and using pointers, we can traverse these lists simultaneously, always picking the smallest current element to add to our result list. This approach leads to a linear time complexity relative to the total number of elements across the three lists.

We will use a **priority queue** (or a min-heap) to keep track of the smallest elements among the three lists. Here’s the step-by-step algorithm:

1. Initialize a min-heap and add the head (first element) of each of the three linked lists into the heap. The heap will help us efficiently retrieve the smallest element.
2. Create a new linked list to store the merged result.
3. While the heap is not empty:
   - Extract the minimum element from the heap (this is the smallest among the current heads of the lists).
   - Add this minimum element to the merged linked list.
   - If the extracted element has a next node in its original list, push that next node onto the heap.
4. Once the heap is empty, we will have a fully merged linked list.

**Example:** For input lists:
- List 1: 1 -> 4 -> 5
- List 2: 1 -> 3 -> 4
- List 3: 2 -> 6
The min-heap will help us merge these lists into:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Here’s the Python code implementing the above approach:
```python
import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

dummy = ListNode(0)
    current = dummy

while min_heap:
        # Extract the smallest node
        val, node = heapq.heappop(min_heap)
        current.next = ListNode(val)
        current = current.next
        # If there is a next node, add it to 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 elements across the three lists and k is the number of lists (in this case, k=3). Each insertion and extraction operation on the heap takes logarithmic time, and we perform these operations for each element in the combined list. The space complexity is **O(k)** due to the storage needed for the heap, as we only store the current heads of the three lists.

We need to consider several edge cases specific to this problem:
1. **All lists are empty:** The function should return an empty list.
2. **One list is empty:** If one of the three lists is empty, the function should correctly merge the remaining two lists.
3. **Different lengths of lists:** The function should handle cases where the lists are of unequal lengths.
4. **All lists contain identical elements:** This should still yield a sorted list without duplicates.
5. **Single node lists:** Each list containing only one element should be merged correctly.

Merge K Sorted arrays

Elastic

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

Elastic 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