824 views
2 votes
2 votes

You are given $k$ sorted lists, each containing $m$ integers in ascending order. Assume that (i) the lists are stored as singly-linked lists with one integer in each node, and (ii) the head pointers of these lists are stored in an array.

  1. Write an efficient algorithm that merges these k sorted lists into a single sorted list using $\theta (k)$ additional storage.
  2. How would you modify your algorithm if you were permitted to use only constant additional storage?

Analyse the time complexity of your algorithm for each of the above two cases.

2 Answers

1 votes
1 votes

a) Efficient way would be the use of MinHeaps without bothering about extra space.

Approach: Use of Min Heaps

  1. Creating a MinHeap (PriorityQueue)
  2. Inserting the first element of K linked lists.
  3. Dequeue the top element of Minheap.
  4. Insert it in the output list.
  5. Insert the next element from the linked list whose element is removed.
  6. Repeat until there is no more element left in the MinHeap.

The time complexity of this approach is  $O( mK * log_2 K)$.


b)  Approach 1: Naive solution 

  1. Initialize the first list of K lists as the Output list.
  2. Traverse from the second list to the Kth List.
    • Insert every node of the currently traversed list into the Output list in a sorted way.

The time complexity of this approach is  $O(N^2)$ where N = k*m

Approach 2: Use of Divide & Conquer approach (similar to MERGE procedure of Merge sort)

  1. Assume each of the K sorted lists of size m as a single module and successively merge two lists at a time up to K.
  2. Now for the K/2 sorted lists of size 2m, merge two of the lists at a time up to K/2.
  3. Similarly, there are K/4 sorted lists of size 4m and we merge them.
  4. Repeat the above process for $log_2 K$ 

The time complexity of this approach is  $O(mK*log_2 K)$ because the outer loop runs log K times and every time it processes m*K elements.

In both of the above approaches, we don’t need any extra space considering the fact that we implement them iteratively and not recursively which will account extra function call stack space.

0 votes
0 votes

We have k sorted lists

Each have m integers in ascending order

To merge these lists in ascending order first we merge 2 sorted list, then next two lists... like that we can merge in O(mk log m) times

mergeLists(list1,list2)
{
    while(list1 && list2)
    {
        if(list1.val<list2.val)
        {
            temp.next=list1;
            list1=list1.next;
            temp=temp.next;
        }
        else{
            temp.next=list2;
            list2=list2.next;
            temp=temp.next;
        }
    return temp.next;
    }
}

Related questions

3 votes
3 votes
4 answers
2
go_editor asked Jun 3, 2016
717 views
Solve the following recurrence ($n$ is a natural number):$$T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$$
4 votes
4 votes
0 answers
3