In computer science, k-way merge algorithms or multiway merges are a specific type of sequence merge algorithms that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges.
The k-way merge problem consists of merging k sorted arrays to produce a single sorted array with the same elements. Denote by n the total number of elements. n is equal to the size of the output array and the sum of the sizes of the k input arrays. For simplicity, we assume that none of the input arrays is empty.
K-way Merge pattern is very useful to solve the problems whenever we are given K sorted arrays, we can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays.
We can also remove the top element from the heap to get the smallest element and push the next element from the same array, to which this smallest element belonged, to the heap. We can repeat this process to make a sorted traversal of all elements.
Create an output array of size (N * K) and then copy all the elements into the output array followed by sorting.
Create an output array of size N * K. Traverse the matrix from start to end and insert all the elements in the output array. Sort and print the output array.
Time Complexity: O(N * K * log (N*K)), Since the resulting array is of size N*K.
Space Complexity: O(N * K), The output array is of size N * K.
LeetCode 23 - Merge k Sorted Lists [hard]
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
We need to find the smallest element of all the input lists. To do so, we have to compare only the smallest element of all the lists first. Once we have the smallest element, we can put it in the merged list.
Following a similar pattern, we can then find the next smallest element of all the lists to add it to the merged list.
Solution 1:
from heapq import heappush, heappop
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0:
return None
heap = []
for i, l in enumerate(lists):
if l:
heappush(heap, (l.val, i))
if len(heap) == 0:
return None
head = cur = ListNode(-1)
while heap:
val, i = heappop(heap)
cur.next = ListNode(val)
cur = cur.next
lists[i] = lists[i].next
if lists[i]:
heappush(heap, (lists[i].val, i))
return head.next
Time Complexity: O(N log K) where N is the total number of elements in all the K input arrays. Space Complexity: O(K)
Solution 2:
from queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
""" :type lists: List[ListNode]
:rtype: ListNode """
class Wrapper():
def __init__(self, node):
self.node = node
def __lt__(self, other):
return self.node.val < other.node.val
head = point = ListNode(0)
q = PriorityQueue()
for l in lists:
if l:
q.put(Wrapper(l))
while not q.empty():
node = q.get().node
point.next = node
point = point.next
node = node.next
if node:
q.put(Wrapper(node))
return head.next
4. Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Solution 1:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
res = nums1 + nums2
res.sort()
if len(res)%2 != 0:
return res[len(res) // 2]
else:
return (res[len(res) // 2 - 1] + res[len(res) // 2]) / 2
Solution 2:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums1.extend(nums2)
nums1 = sorted(nums1)
if len(nums1) % 2 == 0:
n = len(nums1) // 2
return (nums1[n - 1] + nums1[n]) / 2
else:
n = (len(nums1) // 2) + 1
return nums1[n - 1]
