Merge k Sorted Lists Cont…(Divide and Conquer)

Question: Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

You can view the full question here.

Approach 3: Before we head to understanding this solution let’s quickly study what has not worked for us so far.

• Approach 1: Using Tree structure was quite straight forward. But every time a new node needs to be added, it costs us θ(log(n)). And therefore the total cost for k lists with n nodes each will be comparable to θ((n x k) x log(n))
• Approach 2: This time we went all out! We tried extrapolating the logic we used for merging two sorted lists to handle k lists. Ouch! That hurt. The run time was in terms of θ((n x k) x k), where (n x k) represents the total number of nodes in all the lists put together and k represents the total number of lists.
• Approach 3_a: In this next step, we try to leverage on the code already designed to merge two sorted lists. This was a naive approach and turned out to give a time out error even for the simplest of inputs. The reason for this was that the mainList holder was growing in size in every step. And since the RunTime of the merge 2 sorted lists implementation depends on the size of the longest of the two lists, the Runtime also kept increasing in steps of n!!! To Visualize this —

Step 1: Merging Lists A and B

Step 2: Merging the output of Step 1 with List C

Step 3: Merging D to the previous step’s result

The final output

Well if there were only three lists this seems only fair. But if it is a long list of lists, then this can turn out to be extremely expensive. Let’s take a quick peek at the faulty code before diving into the final implementation.

//Approach 3_a
//Runtime: Time out!
//Memory usage: N/A
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode mainList = null;
        if(lists!=null && lists.length>0){
            mainList = lists[0];
        }
        ListNode output = mainList;
        for(int i = 0; i<lists.length; i++){
            mainList = mergeTwoLists(mainList, lists[i]);
        }
        return output;
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         ListNode mainList;
         ListNode valueList;
         if((l1!=null && l2!=null && l1.val<l2.val) || (l1!=null && l2==null)){
             mainList = l1;
             valueList = l2;
         } else{
             mainList = l2;
             valueList = l1;
         }
         ListNode output=mainList;
   for(;valueList!=null;valueList = valueList.next){
             for(;mainList!=null && mainList.next!=null && valueList.val>=mainList.next.val; mainList = mainList.next);
             if(mainList!=null) {
              ListNode tempValue = new ListNode(valueList.val);
              tempValue.next = mainList.next;
              mainList.next = tempValue;
              mainList = mainList.next;
             } else {
              mainList = valueList;
             }
         }
   return output;
     }
}

• After some poking around it was finally established that we need to avoid those unnecessary checks/iterations that are caused when the two lists being compared start to have great disparity in their lengths. If you look at the previous image indicating Step 2, you will notice grey boxes indicating such redundant checks. Here is a great article you can check out for more information.

Now, the final solution is to adopt a divide-and-conquer approach, where you merge the lists in pairs. And iterate until you are left with only one list. This way you can reduce the RunTime to θ(n x log(k)). To visualize the same problem we just used in the approach 3_a —

Combining Lists in pairs at every step

Final output

Now you may check out the code.

//Approach 3_b
//Runtime: 4ms
//Memory usage: 39.4MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //Initialize the List
        List<ListNode> l = new ArrayList();
        for(ListNode node : lists){
            l.add(node);
        }
        //log(n) iterations
        while(l.size()>1){
            int upto = l.size();
            List<ListNode> tempL = new ArrayList();
            //Halving the List length by combining lists of              combarable sizes
            for(int i = 0; i<upto; i=i+2){
                ListNode first = l.get(i);
                ListNode second = null;
                if((i+1)<upto){
                    second = l.get(i+1);
                }
                tempL.add(mergeTwoLists(first, second));
            }
            l = tempL;
        }
        return (l.size()>0? l.get(0): null);
    }
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         ListNode mainList;
         ListNode valueList;
         if((l1!=null && l2!=null && l1.val<l2.val) || (l1!=null && l2==null)){
             mainList = l1;
             valueList = l2;
         } else{
             mainList = l2;
             valueList = l1;
         }
         ListNode output=mainList;
   for(;valueList!=null;valueList = valueList.next){
             for(;mainList!=null && mainList.next!=null && valueList.val>=mainList.next.val; mainList = mainList.next);
             if(mainList!=null) {
              ListNode tempValue = new ListNode(valueList.val);
              tempValue.next = mainList.next;
              mainList.next = tempValue;
              mainList = mainList.next;
             } else {
              mainList = valueList;
             }
         }
   return output;
     }
}

Find more posts here.

Cheers & Chao!