Merge k Sorted Lists

Question

The task is taken from LeetCode

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

I'm struggling with the solution as none of them seem to be very fast:

My solution 1

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  let pointer;
  let firstElement = null;
  while (!lists.every(x => x === null)) {
    let min;
    let iMin;
    for (let i = 0; i < lists.length; i++) {
      if (lists[i] && (min === void 0 || min > lists[i].val)) {
        min = lists[i].val;
        iMin = i;
      }
    }
    if (!firstElement) {
      firstElement = lists[iMin];
    } else {
      pointer.next = lists[iMin];        
    }
    pointer = lists[iMin];
    if (!lists[iMin].next) {
       lists.splice(iMin,1);        
    } else {
       lists[iMin] = lists[iMin].next;    
    }        
  }
  return firstElement;
};

Runtime O(k n)

My solution 2

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1 || !l2) { return l1 ? l1 : l2; }
    let first = null;
    let pointer = null;
    while(l1 || l2) {
      let current;
      if (!l1 || !l2) {
        current = l1 ? l1 : l2;

        if (!first) { return current; }

        pointer.next = current;
        return first;
      }

      if (l1.val < l2.val) {
        current = l1;
        l1 = l1.next;
      } else {
        current = l2;
        l2 = l2.next;
      }        

      if (first) {
        pointer.next = current;
      } else {
        first = current;
      }
      pointer = current;
    }
    return first;
  }

  return lists.reduce((ac, l) => mergeLists(ac, l));

};

Runtime O(n log k)

with k the number of lists elements.

EDIT:

Not really my solution because I read them up and then played around with it:

My solution 3

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    if (l1.val < l2.val) {
      l1.next = mergeLists(l1.next, l2);
      return l1;
    } else {
      l2.next = mergeLists(l2.next, l1);
      return l2;
    }
  }

  return lists.reduce((ac, l) => mergeLists(ac, l));

};

My solution 4

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    if (l1.val < l2.val) {
      l1.next = mergeLists(l1.next, l2);
      return l1;
    } else {
      l2.next = mergeLists(l2.next, l1);
      return l2;
    }
  }
  let i = lists.length;
  while(i-- >= 2) {
    const l1 = lists.shift();
    const l2 = lists.shift();
    lists.push(mergeLists(l1,l2));
  }
  return lists[0];
};

The solution 3 is just as slow as the other first two. But solution 4 is nearly 3 times as fast, eventhough I just replaced the while loop with the reduce function (reduce is at the end of the day also a loop; but how come the difference is that big?)

Also when I applied the following ecmascript6 syntax to solution 4 it would then be even slower than the other solutions:

var mergeKLists = function(lists) {
  if (!lists || !lists.length) { return null; }
  const mergeLists = (l1, l2) => {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    if (l1.val < l2.val) {
      l1.next = mergeLists(l1.next, l2);
      return l1;
    } else {
      l2.next = mergeLists(l2.next, l1);
      return l2;
    }
  }
  let i = lists.length;
  while(i-- >= 2) {
    // const l1 = lists.shift();
    // const l2 = lists.shift();

    // start making changes
    const [l1, l2, ...rest] = lists;
    lists = rest;
    // end making changes
    lists.push(mergeLists(l1,l2));
  }
  return lists[0];
};

Does deconstructing has such a negative impact on performance?

Answer 1

Strategies

It would have been good to summarize the key points and strategies of the different implementations. Mostly for yourself, to clarify your thinking and solidify your understanding. Secondly for reviewers :-) Let me take a jab at that now.

Solution 1

• while there are lists to merge
• find the minimum head and merge it
• update the list with the minimum head or remove it

⇒ The weakness of this solution is the linear step of finding the minimum head. A significant improvement would be to use something better. For example, you could put the lists in a heap. Then finding the list with the minimum head would become logarithmic.

Solution 2

• reduce the lists, using a helper function that merges two lists
• the helper function uses a loop to traverse the lists

⇒ The weakness of this solution is the reduce step is sub-optimal. It merges the lists into a single growing list. A significant improvement would be to use a divide and conquer approach: merge the first \$k/2\$ lists and the last \$k/2\$ lists, merge their result, and apply this logic recursively. They key is dividing intervals in half.

Solution 3

• reduce the lists, using a helper function that merges two lists
• the helper function uses recursion to traverse the lists

⇒ The weakness of this solution is the same as the previous: the reduce is not using divide and conquer. Whether you use a loop or recursion doesn't make a difference if the stack limit is not reached during recursion.

Solution 4

• while there are lists to merge
• merge the first two lists, append the resulting list to the end
• the helper function uses recursion to traverse the lists

⇒ This solution implements a divide and conquer logic, and that makes it significantly faster as the input grows. This solution does pass the online judge.

It seems you thought the loop in this solution is the same as what reduce does, and that's not the case, that's the key difference.

Key takeaways

• verify assumptions (how reduce actually works)
• trust what you know: recursion and iteration are equivalent in terms of time complexity. If you see an important difference in the result, then you're probably overlooking a key difference somewhere else, perhaps due to an incorrect assumption
• clear your mind and seek the key differences