Find K Pairs with Smallest Sums

Let ‘arr1’ be [ ‘1’, ‘2’, ‘6’ ] and ‘arr2’ be [ ‘3’, ‘3’, ‘5’ ] and ‘K’ be 3. There are 9 possible (x, y) pairs such that ‘x’ belongs to ‘arr1’ and ‘y’ belongs to ‘arr2’. Among all of them 3 pairs with smaller ‘x’ + ‘y’ are [ (1, 3), (1, 3), (2, 3) ].

The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’ representing the size of ‘arr1’, ‘arr2’, and number of pairs with the smallest sum to be returned respectively. The second line of each test case contains ‘N’ space-separated integers, representing the elements of the first array, ‘arr1’. The last line of the test cases contains ‘M’ space-separated integers, representing the elements of the second array, ‘arr2’.

For each test case, print ‘K’ lines sorted order containing two space-separated integers ‘x’ and ‘y’, where ‘x’ and ‘y’ denotes the value of pairs with the smallest sum. If two or more pairs have an equal sum then print pair with minimum ‘x’ value first. The output of each test case will be printed in a separate line.

You do not need to print anything, it has already been taken care of. Just implement the given function. In the given function, you need to return a 2D array ‘arr[K][2]’, where ‘K’ is the number of pairs required and ‘arr[i][0]’, ‘arr[i][1]’ are the first and second value of ‘i-th’ pair.

1 <= T <= 5 1 <= N, M <= 3000 1 <= K <= N * M <= 5000 1 <= arr1[i], arr2[i] <= 10 ^ 9 Where ‘T’ is the total number of test cases, ‘N’ and ‘M’ are the size of the given first and second array, ‘K’ denotes the number of pairs required with the smallest sum, and ‘arr1[i]’, ‘arr2[i]’ represents the ‘i-th’ elements in the first and second array.

Test case 1: Among all possible pairs (x, y) such that ‘x’ is from [ ‘1’, ‘2’, ‘3’ ] and ‘y’ is from [ ‘4’, ‘5’, ‘6’ ], 3 pairs with the smallest sum are (1, 4) with sum 5, (1, 5) with sum 6, and (2, 4) with sum 6. Test case 2: Two pairs with the smallest sum are (4, 2) and (4, 4) with sum 6 and 8.

Brute Force Approach

The idea is to find all possible pairs (x, y) with their sum ‘x’ + ‘y’ and simply return ‘K’ pairs with the smallest ‘x’ + ’y’ value.

Algorithm:

Let the given arrays be ‘arr1’ and ‘arr2’, and ‘K’ be the no. of pairs required.
Declare a tuple/ struct to store pairs with the sum, for example { x + y, (x, y)}, where ‘x’ and ‘y’ are the first and second values in a pair.
Create a list of tuples say ‘allPairs’ to store pairs.
Run a loop for each element in ‘arr1’.
- Run a loop for each element in ‘arr2’
  - Add { arr1[i] + arr2[j] , (arr1[i], arr2[j]) } in ‘allPairs’.
Sort the list ‘allPairs’ in ascending order according to the sum. i.e. first element in the tuple.
Return the first ‘K’ pairs from the list ‘allPairs’.

Time Complexity

O( N * M * log(N * M) ), where ‘N’ and ‘M’ are the sizes of given first and second arrays respectively.

As there are ‘N * M’ possible pairs from the given first and second array, and we checking each pair exactly once and then sorting them in ascending order that takes the overall O (N * M * log(N * M)) time complexity.

Space Complexity

O( N * M ), where ‘N’ and ‘M’ are the sizes of given first and second arrays respectively.

As there are ‘N * M’ possible pairs from the given first and second array, and we need to store each pair exactly once that takes O (N * M) space complexity.

Find K Pairs with Smallest Sums

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2:

Algorithm: