what is time complexity of this code (from leetcode)?

Question

The problem is "Merge k sorted linked lists and return it as one sorted list. " from leetcode

1.

My solution is to use a vector to maintain the current position of each linked list, sort the vector to get the node with minimal value and insert it at the end of the merged list. Here is the code:

bool cmp(ListNode *a, ListNode *b) {
return a->val < b->val;
}
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
    ListNode *dummy = new ListNode(-1);
    ListNode *curr = dummy;

    //init
    vector<ListNode*> currNodes;
    for(int i = 0; i < lists.size(); ++i){
        if(lists[i] != NULL){
            currNodes.push_back(lists[i]);
        }
    }

    while(!currNodes.empty()){
        sort(currNodes.begin(), currNodes.end(), cmp);
        curr->next = currNodes[0];
        curr = curr->next;

        if(currNodes[0]->next != NULL){
            currNodes.push_back(currNodes[0]->next);
        }
        currNodes.erase(currNodes.begin());
    }

    return dummy->next;
}
};

Since the time complexity of std::sort is nlog(n) and we have (n1+n2...nk) iterations, thus I suppose the total time complexity is O((n1+n2...+nk)klog(k)). But at each iteration, the size of vector currNodes may vary so I'm a little bit confused. Can anyone confirm this?

2. Also I saw another solution on leetcode discussion forum which use the thought of "merge sort". It merges two linked list everytime.

public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if(lists.isEmpty()) return null;
    if(lists.size() == 1) return lists.get(0);
    int k = lists.size();
    int log = (int)(Math.log(k)/Math.log(2));
    log = log < Math.log(k)/Math.log(2)? log+1:log; // take ceiling
    for(int i = 1; i <= log; i++){
        for(int j = 0; j < lists.size(); j=j+(int)Math.pow(2,i)){
            int offset = j+(int)Math.pow(2,i-1);
            lists.set(j, mergeTwoLists(lists.get(j), (offset >= lists.size()? null : lists.get(offset))));
        }
    }
    return lists.get(0);
}


public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    ListNode head = l1.val > l2.val? l2:l1;
    if(head.equals(l2)){
        l2 = l1;
        l1 = head;
    }
    while(l1.next != null && l2 != null){
        if(l1.next.val > l2.val){
            ListNode tmp = l1.next;
            l1.next = l2;
            l2 = l2.next;
            l1 = l1.next;
            l1.next = tmp;
        }
        else
            l1 = l1.next;
    }
    if(l2 != null){
        l1.next = l2;
    }
    return head;
}
}

I wonder what is the time complexity of this solution? Since it merges two linked lists every time, there is log(n) iterations. But the linked list gets longer (since it's merged from two linked lists) after each iteration, how to compute the time complexity at each iteration and then add them up together?

Thank you in advance :)

Answer 1

here is my solution. the complexity is (finding 1 min from k lists)*(n nodes) i would say its O(kn) where k is the number of lists the optimal solution would be O(nlogk) see here: How to sort K sorted arrays, with MERGE SORT

but that's just enough for leetcode already so i didnt do the min-heap

// http://oj.leetcode.com/problems/merge-k-sorted-lists/

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    ListNode cursor = new ListNode(Integer.MAX_VALUE);
    ListNode head = cursor;
    int min = Integer.MAX_VALUE;
    int index = -1;
    while(lists.size()>0){
        for(int i=0; i<lists.size(); i++){//get 1 min
            if(lists.get(i)!=null && lists.get(i).val<min){
                min = lists.get(i).val;
                index = i;
            }
            if(lists.get(i)==null){
                lists.remove(i);
                i--;
            }
        }
        if(index>=0){//put the min in
            cursor.next = lists.get(index);
            cursor = cursor.next;
            lists.set(index,lists.get(index).next);
            if(lists.get(index)==null){
                lists.remove(index);
            }
            min = Integer.MAX_VALUE;
        }
    }
    return head.next;
}

Answer 2

I think there is O((n1+n2+n3..nk)logk) solution for this problem where you do following:-

1. Add first k element to min heap
2. remove the min element and add into new list
3. remove next element from list which contained the min element and add to heap.
4. continue till heap is empty.

More interesting solution : -

Use merge sort like merging routine with huffman encoding like selection :-

Suppose you have k list with n elements each : -

1. Add all lists with there sizes as key into min heap
2. Select two smallest lists and merge them using merge sort like routine
3. Add the new list into heap with its size as key
4. 1 to 3 till only one list remains, that list is your merged sorted list.

If there are k lists with n elements each then huffman like merging will give following time complexity:-

1. removing two lists from heap takes O(logk)
2. merge sort like merging takes O(n1+n2)

Logical iterations in the algorithm : -

1. merges all pairs from n lists of size n taking n/2*(n+n) = O(n^2)
2. merges all pairs from n/2 lists of size n/4*(2n+2n) = O(n^2) ... done till O(logK) iterations.

Time Complexity : O(n^2*logk)