1 month

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


Responses(0)







Related