5 months

# Coding Patterns: K-way Merge

In computer sciencek-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 push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum. While inserting elements to the Min Heap we keep track of which array the element came from.

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.

## Naive Approach for Merging k sorted arrays:

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.

1. We can push the smallest (first) element of each sorted array in a Min Heap to get the overall minimum.
2. After this, we can take out the smallest (top) element from the heap and add it to the merged list.
3. After removing the smallest element from the heap, we can insert the next element of the same list into the heap.
4. We can repeat steps 2 and 3 to populate the merged list in sorted order.

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
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))

Time ComplexityO(N log K) where N is the total number of elements in all the K input arrays.  Space ComplexityO(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
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))

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 =       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]

#### Responses(0)  Related