23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• 104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

This problem is in fact very similar to merging two linked lists. Just like that problem, we need a way to somehow efficiently compare $k$ numbers and insert the lowest number until we have no more elements to insert into the answer linked list. The fact that we have multiple changing numbers but we need to always know the lowest one calls for a priority queue, and thus a heap approach.

The second question to answer is how we track a given number, once we have determined the smallest one, and link it back to the linked list it belongs to. We can use the index of the linked list to do this, and store a number in the heap as either a tuple (number, index) or use a hash table to track this independently.

The approach is then clear.

1. Initialise the heads of each list as a heap, tracking their original linked lists.
2. While there are elements in any list, pop off the smallest number from the heap and add it to the answer linked list.
3. Increment the linked list where the smallest number came from to the next node, and push its value onto the heap if it is not null.
4. Repeat steps 2 and 3 until there are no more elements in any list, and return the answer linked list.

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
	import heapq
	head = ListNode() # empty ListNode to reach beginning of linked list
	curr = head
	
	# initialise heap
	heap = [(lists[i].val, i) 
			for i in range(len(lists)) 
			if lists[i] is not None]
	heapq.heapify(heap)
	
	while heap:
		smallest, index = heapq.heappop(heap)
		curr.next = ListNode(smallest)
		curr = curr.next
		
		# update the heap and lists if needed
		lists[index] = lists[index].next
		if lists[index] is not None:
			heapq.heappush(
				heap, 
				(lists[index].val, index)
			)
	
	return head.next

Time Complexity

First, initialising the heap takes $\mathcal{O}(k)$, and in the worst case $k \in \mathcal{O}(n)$ (consider $n$ lists of 1 element), so initialising the heap takes $\mathcal{O}(n)$ time. Next is the loop: each iteration has some constant time assignments and at most 2 heap operations, taking $\mathcal{O}(\log n)$ time. This loops $n$ times through all nodes in all $k$ linked lists, so the loop takes in total $\mathcal{O}(n\log n)$ time. This dominates the heapify operation, so the total run time complexity is in $\mathcal{O}(n \log n)$.

Space Complexity

Notice the heap takes $\mathcal{O}(k)$ space complexity and therefore $\mathcal{O}(n)$ by the same argument for the heapify operation. All other variables take constant space, so the total space complexity is in $\mathcal{O}(n)$.

Divide & Conquer

This problem is a generalisation of question 21. We know there is a way to solve that in $\mathcal{O}(n)$ time with constant space, so if we can reduce this problem down to the two sorted lists problem, we can solve this efficiently. The question is then how can we convert $k$ sorted lists into 2 sorted lists? This is where a divide and conquer strategy works wonders: if we can combine $\frac{k}{2}$ lists into 2 lists, then doing so results in 2 sorted lists - and with this logic we can divide all the way down until there are only 2 lists to combine, and then work our way back up to combine $k$ total lists.

def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
	"""Combine list1 and list2 into a single sorted linked list."""
	...

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
	if len(lists) == 0: return None
	if len(lists) == 1: return lists[0]
	if len(lists) == 2: return mergeTwoLists(lists[0], lists[1])

	k = len(lists)
	left_lists = mergeKLists(lists[:k // 2])
	right_lists = mergeKLists(lists[k // 2:])

	return mergeTwoLists(left_lists, right_lists)

Time Complexity

From question 21, mergeTwoLists takes $\mathcal{O}(n)$ time, and every other non-recursive operation is constant time. Since we are always dividing the list lengths in half, there are going to be $\log_2(k)$ divisions and therefore $\log_2(k)$ calls to mergeKLists. Therefore there are $\log_2(k)$ calls each in $\mathcal{O}(n)$ time, so the total time complexity of the algorithm is in $\mathcal{O}(n\log k)$ time.

Space Complexity

Each call takes constant space, but there are $\log_2(k)$ calls to mergeKLists - so the total space complexity is in $\mathcal{O}(\log k)$.