K-way Merge Problems Flashcards
Merge K Sorted Lists
Given an array of ‘K’ sorted LinkedLists, merge them into one sorted list.
Example 1
Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
Output: [1, 2, 3, 3, 4, 6, 6, 7, 8]
Example 2
Input: L1=[5, 8, 9], L2=[1, 7]
Output: [1, 5, 7, 8, 9]
A brute force solution could be to add all elements of the given ‘K’ lists to one list and sort it. If there are a total of ‘N’ elements in all the input lists, then the brute force solution will have a time complexity of O(N*logN) as we will need to sort the merged list. Can we do better than this? How can we utilize the fact that the input lists are individually sorted?
If we have to find the smallest element of all the input lists, we have to compare only the smallest (i.e. the first) element of all the lists. 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.
The best data structure that comes to mind to find the smallest number among a set of ‘K’ numbers is a Heap. Let’s see how can we use a heap to find a better algorithm.
- We can insert the first element of each array in a Min Heap.
- After this, we can take out the smallest (top) element from the heap and add it to the merged list.
- After removing the smallest element from the heap, we can insert the next element of the same list into the heap.
- We can repeat steps 2 and 3 to populate the merged list in sorted order.
Since we’ll be going through all the elements of all arrays and will be removing/adding one element to the heap in each step, the time complexity of the above algorithm will be O(N*logK), where ‘N’ is the total number of elements in all the ‘K’ input arrays.
The space complexity will be O(K) because, at any time, our min-heap will be storing one number from all the ‘K’ input arrays.
Kth Smallest Number in M Sorted Lists
Given ‘M’ sorted arrays, find the K’th smallest number among all the arrays.
Example 1
Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4], K=5
Output: 4
Explanation: The 5th smallest number among all the arrays is 4, this can be verified from the merged list of all the arrays: [1, 2, 3, 3, 4, 6, 6, 7, 8]
Example 2
Input: L1=[5, 8, 9], L2=[1, 7], K=3
Output: 7
Explanation: The 3rd smallest number among all the arrays is 7.
This problem follows the K-way merge pattern and we can follow a similar approach as discussed in Merge K Sorted Lists.
We can start merging all the arrays, but instead of inserting numbers into a merged list, we will keep count to see how many elements have been inserted in the merged list. Once that count is equal to ‘K’, we have found our required number.
A big difference from Merge K Sorted Lists is that in this problem, the input is a list of arrays compared to LinkedLists. This means that when we want to push the next number in the heap we need to know what the index of the current number in the current array was. To handle this, we will create a Node class which will track the array and the element indices.
Since we’ll be going through at most ‘K’ elements among all the arrays, and we will remove/add one element in the heap in each step, the time complexity of the above algorithm will be O(K*logM) where ‘M’ is the total number of input arrays.
The space complexity will be O(M) because, at any time, our min-heap will be storing one number from all the ‘M’ input arrays.
Kth Smallest Number in a Sorted Matrix
Given an N * N matrix where each row and column is sorted in ascending order, find the Kth smallest element in the matrix.
Example
Input: Matrix=[[2, 6, 8],
[3, 7, 10],
[5, 8, 11]], K=5
Output: 7
Explanation: The 5th smallest number in the matrix is 7.
This problem follows the K-way merge pattern and can be easily converted to Kth Smallest Number in M Sorted Lists. As each row (or column) of the given matrix can be seen as a sorted list, we essentially need to find the Kth smallest number in ‘N’ sorted lists.
First, we inserted at most ‘K’ or one element from each of the ‘N’ rows, which will take O(min(K, N)). Then we went through at most ‘K’ elements in the matrix and remove/add one element in the heap in each step. As we can’t have more than ‘N’ elements in the heap in any condition, therefore, the overall time complexity of the above algorithm will be O(min(K, N) + K*logN).
The space complexity will be O(N) because, in the worst case, our min-heap will be storing one number from each of the ‘N’ rows.
Smallest Number Range
Given ‘M’ sorted arrays, find the smallest range that includes at least one number from each of the ‘M’ lists.
Example 1
Input: L1=[1, 5, 8], L2=[4, 12], L3=[7, 8, 10]
Output: [4, 7]
Explanation: The range [4, 7] includes 5 from L1, 4 from L2 and 7 from L3.
Example 2
Input: L1=[1, 9], L2=[4, 12], L3=[7, 10, 16]
Output: [9, 12]
Explanation: The range [9, 12] includes 9 from L1, 12 from L2 and 10 from L3.
This problem follows the K-way merge pattern and we can follow a similar approach as discussed in Merge K Sorted Lists.
We can start by inserting the first number from all the arrays in a min-heap. We will keep track of the largest number that we have inserted in the heap (let’s call it currentMaxNumber).
In a loop, we’ll take the smallest (top) element from the min-heap and currentMaxNumber has the largest element that we inserted in the heap. If these two numbers give us a smaller range, we’ll update our range. Finally, if the array of the top element has more elements, we’ll insert the next element to the heap.
We can finish searching the minimum range as soon as an array is completed or, in other terms, the heap has less than ‘M’ elements.
Since, at most, we’ll be going through all the elements of all the arrays and will remove/add one element in the heap in each step, the time complexity of the above algorithm will be O(N*logM) where ‘N’ is the total number of elements in all the ‘M’ input arrays.
The space complexity will be O(M) because, at any time, our min-heap will be store one number from all the ‘M’ input arrays.
K Pairs with Largest Sums
Given two sorted arrays in descending order, find ‘K’ pairs with the largest sum where each pair consists of numbers from both the arrays.
Example 1
Input: L1=[9, 8, 2], L2=[6, 3, 1], K=3
Output: [9, 3], [9, 6], [8, 6]
Explanation: These 3 pairs have the largest sum. No other pair has a sum larger than any of these.
Example 2
Input: L1=[5, 2, 1], L2=[2, -1], K=3
Output: [5, 2], [5, -1], [2, 2]
This problem follows the K-way merge pattern and we can follow a similar approach as discussed in Merge K Sorted Lists.
We can go through all the numbers of the two input arrays to create pairs and initially insert them all in the heap until we have ‘K’ pairs in Min Heap. After that, if a pair is bigger than the top (smallest) pair in the heap, we can remove the smallest pair and insert this pair in the heap.
We can optimize our algorithms in two ways:
- Instead of iterating over all the numbers of both arrays, we can iterate only the first ‘K’ numbers from both arrays. Since the arrays are sorted in descending order, the pairs with the maximum sum will be constituted by the first ‘K’ numbers from both the arrays.
- As soon as we encounter a pair with a sum that is smaller than the smallest (top) element of the heap, we don’t need to process the next elements of the array. Since the arrays are sorted in descending order, we won’t be able to find a pair with a higher sum moving forward.
Since, at most, we’ll be going through all the elements of both arrays and we will add/remove one element in the heap in each step, the time complexity of the above algorithm will be O(N*M*logK) where ‘N’ and ‘M’ are the total number of elements in both arrays, respectively.
If we assume that both arrays have at least ‘K’ elements then the time complexity can be simplified to O(K2logK), because we are not iterating more than ‘K’ elements in both arrays.
The space complexity will be O(K) because, at any time, our Min Heap will be storing ‘K’ largest pairs.
