Yesterday, I looked into solving the merge K sorted lists problem on LeetCode. The difficulty level was hard, but it has an acceptance rate of 59.7%. So it may be hard, but a fair few people have solved this. Here is the problem.
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 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted linked list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
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.
Now let’s look through the features of this problem. It involves linked lists, so retrieval of a value in a linked list will have to be O(n). The length of the list is 0 < k < 104, while the length of the linked list is also 0 < n < 104. The value in a linked list could be negative or positive, and the linked list is sorted in ascending order, but the surrounding list is not.
Each linked list is sorted in ascending order, so no need to traverse each linked list to find the smallest. You could have an early return for empty linked lists if all the linked lists in the list are also empty. We could consider the use of a pointer or two pointers to traverse the list and break the list into parts, sorting each of those parts. That gives the possibility of a recursive approach, as there is an early return statement in an iteration of the list where the iteration has a linked list that has a length of 1 or 0.
But first, I decided to look into a normal iterative approach, which takes advantage of pointers, so the space used, the memory used, is minimized. Hence, I have two approaches to consider: a recursive approach and an iterative approach.
Now let’s break down the iterative approach step by step. In each step, we iterate through the list, we move the smallest value and append it to the results of the linked list while moving the head of the linked list forward, traversing the linked list at each iteration. So, it is possible to keep going to consistently loop through the list, removing the smallest value, and adding to our results. So it is possible to keep traversing a certain linked list, removing the smallest value and adding to our result at a certain step in the iteration of the list.
But in this step, we need to know what the smallest element is. So that we can make sure that the element that we are removing from that certain linked list is actually the smallest. So at every step of the iteration of the list, we need to know the smallest element in the rest of the surrounding list.
Thanks to the fact that all the linked lists are sorted in ascending order, we know that the head of a linked list is always the smallest in that linked list. So we just need to traverse the list to find the smallest value in the other linked list, which would be the head at the time. If the value in the current linked list is being looked at, if the value of the smallest elements in the other linked list is larger than the element in the current linked list, larger than the head of the current linked list, then that element is the smallest at the time.
But this requires us to consistently traverse the list to find the smallest value that is not in the current linked list. That may add some latency. Now that we’ve thought out the strategy, let us write some code to implement it.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[Optional[ListNode]]
:rtype: Optional[ListNode]
"""
dummy = ListNode()
result = dummy
while(len(lists)>0):
for i, x in enumerate(lists):
j = (i + 1) % len(lists)
if lists[j] == None:
lists.pop(j)
continue
smallest_head = lists[j]
for k in range(1, len(lists)):
if lists[(j+k) % len(lists)] == None:
continue
if smallest_head.val > lists[(j+k) % len(lists)].val:
smallest_head = lists[(j+k) % len(lists)]
while lists[i] != None and lists[i].val <= smallest_head.val:
result.next = ListNode(lists[i].val)
result = result.next
lists[i] = lists[i].next
if lists[i] == None:
lists.pop(i)
return dummy.nextThis implementation passed the initial tests but failed when the input included a large list of linked lists with a length greater than 100. This gave me a time limit exceeded error. This meant my algorithm was simply not efficient enough.
When I started to understand why that was the case, I noticed I had not accounted for the duplicates in the values. We could reduce the amount of iterations made by just removing the duplicates and keeping a store of the frequency of each value from the inputs. This frequency can be used when writing the results, which would be a lot more efficient. So I adjusted the algorithm to remove duplicates by storing them in a dictionary, having the value of the element be the key and the frequency of the element in the input be the value. Here is the new code implementation.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[Optional[ListNode]]
:rtype: Optional[ListNode]
"""
nums = dict()
for i, x in enumerate(lists):
dummy = ListNode()
curr = lists[i]
dummy.next = curr
before = dummy
while curr != None:
if curr.val in nums:
nums[curr.val] += 1
before.next = curr.next
else:
nums[curr.val] = 1
before = before.next
curr = curr.next
lists[i] = dummy.next
dummy = ListNode()
result = dummy
while(len(lists)>0):
for i, x in enumerate(lists):
j = (i + 1) % len(lists)
if lists[j] == None:
lists.pop(j)
continue
smallest_head = lists[j]
for k in range(1, len(lists)):
if lists[(j+k) % len(lists)] == None:
continue
if smallest_head.val > lists[(j+k) % len(lists)].val:
smallest_head = lists[(j+k) % len(lists)]
while lists[i] != None and lists[i].val <= smallest_head.val:
for q in range(nums[lists[i].val]):
result.next = ListNode(lists[i].val)
result = result.next
lists[i] = lists[i].next
if lists[i] == None:
lists.pop(i)
return dummy.nextThis implementation was accepted, yay! Now let’s look at the metrics. The total runtime is 234 milliseconds with a total memory use of 17.7MB. My runtime solution beat 7.05%, which was pretty bad, but it’s all good because our memory score beat 100% of all the other solutions. I believe that the reason why my solution had so much latency is because of the process of finding the smallest value, the smallest element in all the other linked lists that were not the current linked list being looked at every step of the iteration of the list, which would be O(n) at every step. But the used memory is so low because I don’t make use of any arrays in the code, only a hash map, which would grow at a rate of much less than O(n), where n is the list of unique numbers.
Now let’s take a look at the recursive approach. I decided to use recursion that splits the list until there is only one linked list in the input list, then the linked lists are merged into a new sorted linked list. This has major similarities with the recursive merge sort algorithm.
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[Optional[ListNode]]
:rtype: Optional[ListNode]
"""
return pairwise_merge(lists,0,len(lists)-1)
def pairwise_merge(lists, l, h):
if l== h :
return lists[l]
if l < h:
m = (l+h)//2
left = pairwise_merge(lists,l,m)
right = pairwise_merge(lists,m+1,h)
return merge(left,right)
def merge(l1,l2):
tmp1 = l1
tmp2 = l2
newhead = ListNode()
curr= newhead
while tmp1 is not None and tmp2 is not None :
if tmp1.val < tmp2.val :
curr.next = ListNode(tmp1.val)
curr = curr.next
tmp1= tmp1.next
else :
curr.next = ListNode(tmp2.val)
curr = curr.next
tmp2 = tmp2.next
while tmp1 is not None :
curr.next = ListNode(tmp1.val)
curr = curr.next
tmp1= tmp1.next
while tmp2 is not None :
curr.next = ListNode(tmp2.val)
curr = curr.next
tmp2= tmp2.next
return newhead.nextThis implementation was also accepted. This one had a score of 96 milliseconds of runtime, and memory use was 24.02 MB. The runtime improved and beats 77.9% of all solutions, but the memory used got larger. And I believe this… got larger and beats only 5%. This is likely because recursive functions tend to allocate a lot more memory to the function due to the different iterations of the same function call. But the runtime improved.
So these were my two solutions, but what about the most optimal solution in terms of runtime? So I had a look, and it was quite elegant.
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[Optional[ListNode]]
:rtype: Optional[ListNode]
"""
valToList = defaultdict(list)
for i, l in enumerate(lists):
curr = l
while curr:
valToList[curr.val].append(i)
curr = curr.next
res = ListNode(-1)
resIter = res
for val in sorted(valToList.keys()):
for l_idx in valToList[val]:
resIter.next = lists[l_idx]
resIter = resIter.next
lists[l_idx] = lists[l_idx].next
return res.nextThis solution, when accounting for duplicates, did not just store the frequency in a dictionary, it stored the index of the linked list. So when constructing the result, this allows you to simply iterate over the sorted keys of the dictionary and take the index of the value in the array, which is the value of the dictionary, and add the head of the linked list at that index, moving the linked list to the next element after. So you don’t need to know the smallest element at all times. That is simply taken care of by sorting the keys of the dictionary. That’s very clever. Well, there you have it, two implementations for different constraints. You can implement them based on whether your application, the runtime, or the memory is more critical to your application.