LeetCode 23. Merge k Sorted Lists— Graphically Explained Python3 Solution

 

Problem Description

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.

Example:

Input: lists = [[1,1,5],[1,3,4],[2,6]]
Output: [1,1,1,2,3,4,5,6]
Explanation: The linked-lists are:
[
  1->1->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->1->2->3->4->5->6

Solution

Obvious Solution

The obvious (and brute force) way is to navigate ALL list items, save them into an array and then sort. The time complexity is: O(kN + kNLog(kN)) since for for total k Lists (each one with average N elements), I need to visit them all and the quick sort on final array takes kNLog(kN). The space complexity is O(kN) as all values will be saved.

Best Solution (to me)

Since each list is already sorted, I can definitely leverage that. To start with, let me use this example:

To show it more clearer, let me put some twists (showing only the leftmost element of each list):

You can see from above, for all current leftmost elements, “1” (doesn’t matter which “1”, so I just pick the one in the first list) is the smallest element. Although I haven’t looked into all other elements, I’m pretty sure it’s the smallest element of ALL elements. Why? The reason is, within current smallest elemements (of all lists), it’s the smallest: smallest among the smallest :).

So “1” will be picked up as current smallest element and its next element (if any) will become current like below right part:

Then I can repeat the process until all elements are visited.

Additional Tips:

There are 2 additional tips (which I use in the source code):

1. Dummy head of linked list

Detailed illustration can be found within below Cheatsheet article (search “dummy” in it). I recommend reading it before checking following source code.

Python3 Cheatsheet (continuously updated)

Useful Build-in Functions

medium.com

2. Heapq (priority queue)

Detailed illustration of heapq can be found in above Cheatsheet article (search “heapq” in it). I recommend reading it before continue reading.

The heapq is used in source code to achieve O(1) complexity to get smallest element out of a bunch elements. A detail to know for Python3 heaqp is: when I heappush a tuple, by default, tuple[0] will be used to compare with existing tuples’ tuple[0], if there is equal pair, tuple[1] will be used.

So below code may report “TypeError: ‘<’ not supported between instances of ‘ListNode’ and ‘ListNode'”, since (1,n1)[0] == (1,n2)[0] and Python3 will compare n1 and n2 but “<” operator may not be implemented in ListNode class.

import heapq
h = []
n1 = ListNode(1)
n2 = ListNode(1)
heapq.heappush(h, (1, n1))
heapq.heappush(h, (1, n2)) #TypeError: '<' not supported ...

To avoid that, I add a unique counter to the tuple like:

import heapq
h = []
n1 = ListNode(1)
n2 = ListNode(1)
cnt = 0
heapq.heappush(h, (1, cnt, n1))
cnt +=1
heapq.heappush(h, (1, cnt, n2)) 

Time & Space Complexity

Per above illustration and techniques, all elements will be visited once only and for each element, there will be a Heapq push ( O(LogN) where N is the size of heap) and pop (O(1)). Assuming there are k lists and each one has N elements on average, the total elements are kN, and each element will be processed in heapq by O(Logk), the final time complexity is O(kN Logk).

Since I use a heap size of k, the space complexity is O(k).

Source Code