Merge k Sorted Lists


  • 0
    A

    First we need to understand how the solution will get constructed. Later we will see how to construct that solution with optimal time and space complexity.

    Lets say that we have n lists to merge. We will add a single element, one by one, from these lists into our solution list i.e. merged list, that we have to return. Lets say that we want to add an element from listi. Which is the best element from this list that should be considered? It is trivial to see that the first element is the smallest among all the other elements of list (as it is sorted) and since the merged list is also sorted, it would be the best one to pick.

    From above simple yet crucial observation, we present the following lemma:

    Lemma: For the selection of next element of our solution list, from n non-empty sorted lists, it is sufficient to consider only n candidates, each one being the first un-used element of their respective list.

    We now have an approach to solve this problem. We keep n pointers, each pointing to the least unused element of their respective list. Then we take the element, smallest in value, and make it's pointer point to the next element of the list. Note that if current list gets exhausted i.e. the pointer now points to NULL, we will not consider that list anymore, as all of its elements are now taken. Our algorithm terminates when all the pointers point to NULL.

    The challenge here comes when we have to select the element with minimum value among the n candidates we have.

    Approach 1) One way to do so is iterate over all of those candidates and fetch the minimum candidate. But this would make the time complexity O(M * n) where M is the size of final list, as each M insertions will take O(n) time to fetch the best element to insert.

    Time complexity: O(M * n)
    Space complexity: O(n)

    Approach 2) Second approach, better than first one, is to maintain the candidates in a heap/priority queue that can order the elements based on a comparative function. In our case, it is the value of the candidate that will be used to order the elements. The element we need can then be fetched as the top of the queue/heap in O(1) time. We take this element, remove it from queue/heap and insert the next candidate of the list in which this element belonged into the queue/heap. If it was the last element of it's list i.e next element is NULL, we insert nothing. The insertion step has complexity of O(log n) which brings the overall time complexity of the solution to O(M * log n). We use an additional space of only O(n) since in the heap/queue we have no more than n pointers pointing to the candidates.

    Time complexity: O(M * log n)
    Space complexity: O(n)

    class Compare {
    public:
        bool operator()(ListNode* x, ListNode *y) {
            return x->val > y->val;
        }
    };
    
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            priority_queue <ListNode*, vector<ListNode*>, Compare> Q;
            int n = lists.size();
            for (int i = 0; i < n; ++i) {
                if (lists[i] != NULL) {
                    Q.push(lists[i]);
                }
            }
            
            ListNode* res = new ListNode(0);
            ListNode* head = res;
            
            while (!Q.empty()) {
                ListNode* cur = Q.top(); Q.pop();
                if (cur->next) {
                    Q.push(cur->next);
                }
                head->next = new ListNode(cur->val);
                head = head->next;
            }
            return res->next;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.