C++ Program for Find k pairs with Smallest Sums in Two Arrays

Provided 2 ascending integer arrays arr1[] and arr2[] and an integer k. Determine k pairs with the smallest sums, where one element belongs to arr1[] and the other element belongs to arr2[].

Examples:

Method No. 1 (Simple)

Find all of the pairs and record their sums. This step's time complexity is O(n1 * n2), where n1 and n2 are the sizes of the input arrays.

Then sort the pairs by sum. This step's time complexity is O(n1 * n2 * log (n1 * n2)).

• O(n1 * n2 * log (n1 * n2) is the overall time complexity.
• O(n1*n2) is Auxiliary Space.

Method 2 (Potent):

Starting with the smallest sum pair, we discover k smallest sum pairings one by one. The aim is to keep track of all array2[] elements that have already been investigated for each element array1[i1], so that in an iteration we just consider the next element. We utilise an index array indexno2[] to maintain the indexes of the following elements in the other array for this purpose. It simply indicates which element of the second array should be added to the element of the first array in each iteration. For the element that forms the next minimum value pair, we increment the value in the index array.

Implementation in C++:

Output:

(1, 2) (1, 4) (3, 2) (3, 4)

• Time Complexity will be O(k*n1).
• Auxiliary Space will be O(n1).

Method 3: Sorting, Min heap, and Map

Instead of brute forcing our way through all of the available sum combinations, we should develop a strategy to narrow our search space down to possible candidate sum combinations.

1. In C++, create a min heap, i.e. priority_queue, to hold the sum combinations as well as the indices of the components from both arrays A and B that make up the sum. The sum is used to sort the heap.
2. Initialize the heap with the indices of entries from both arrays and the smallest possible sum combination, i.e. (A[0] + B[0]) (0, 0). Inside the min heap, the tuple will be (A[0] + B[0], 0, 0). The heap is ordered by the first value, which is the sum of both items.
3. Pop the heap to acquire the current smallest sum and the element indices that make up the sum. Allow the tuple to be (sum, i, j).
   • Insert (A[i + 1] + B[j], I + 1, j) and (A[i + 1], I j + 1) into the min heap, but make sure that the pair of indices I + 1, j) and I j + 1) are not already present. In C++, we may use set to test this.
   • Return to 4 till K times.

Implementation in C++:

Output:

(1, 2)
(1, 4)
(1, 5)
(1, 9)

• Auxiliary Space will be O(n) because we are utilising additional space.
• Time Complexity will be O(n*logn) assuming k<=n.