Find K Pairs with Smallest Sums

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’.

As the given arrays are sorted, we can easily say that the pair (x, y) gives a minimum sum when ‘x’ and ‘y’ are the first and second elements of ‘arr1’ and ‘arr2’ respectively,i.e. (arr1[0], arr2[0] ). What about the next minimum sum pair? It can be either (arr1[1], arr2[0] ) or (arr1[0], arr2[1] ) as all other pairs must have greater sum. For example, let ‘arr1’ be [1, 2, 3] and ‘arr2’ be [1, 4, 5] the pair with smallest sum will be (arr1[0], arr2[0]), all other pairs have greater sum, As the array are sorted next pair can either be (arr1[0], arr2[1]) or (arr1[1], arr2[0]), In this case the pair will be (arr1[1], arr2[0]), i.e. (2, 1).

So, the overall idea is to maintain a min-heap data structure that stores indices in pair and their sum, the ordering of min-heap is according to sum. Initially, we push the pair (0, 0) as this pair has the smallest sum over all pairs. Now we pop ‘K’ pairs from the min-heap, and while popping a  pair with index (i, j) we add pair (i + 1, j)  and (i, j + 1) as one of these pairs may have the next minimum sum after pair (i, j). Now here we may end up adding the same pair more than one time into the min-heap. For example, if we pop (2, 3), we push (3, 3) and (2, 4) and when we pop (3, 2), we push (4, 2) and (3, 3). We push (3, 3) twice. So to avoid multiple pushes for the same pair, we can use a hashmap say ‘visited’ to keep track of the already pushed pairs. As the min-heap always gives a pair with a minimum sum we can say that we get ‘K’ pairs with the smallest sum after ‘K’ pop operations.

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 { arr1[x] + arr2[y], (x, y) }, where ‘x’ and ‘y’ are the index of first and second values in a pair.
• Declare a min-heap of tuples say ‘allPairs’ to store pairs. The ordering of min-heap is according to the first element of tuples, i.e. sum in pair.
• Declare a list say ‘answer’ to store ‘K’ pairs with the smallest sum.
• Declare a hashmap say ‘visited' that store already pushed pairs.
• Initially push { arr1[0] + arr2[0], (0, 0 ) } into ‘allPairs’.
• Run a loop ‘K’ times.
  • Pop a minimum element from the heap and store it in say ‘currPair’.
  • Add ‘currPair’ in the answer.
  • Push the next possible pairs into a heap i.e let say ‘currPair’ is a pair with index (i, j) then the next possible pairs are with indices (i, j + 1) and (i + 1, j) So,
  • If j + 1 < size of arr2  and (i, j + 1) is not in ‘visited’.
    • push { arr1[i] + arr2[ j + 1 ], (i, j + 1) }.
  • If i + 1 < size of arr1 and (i + 1, j) is not in ‘visited’.
    • push { arr1[ i + 1 ] + arr2[j], (i + 1, j) }.
• Return ‘answer’.

As the given arrays are sorted, we can show that for every element in ‘arr1’ (first array), the pair with minimum sum will have the first element in ‘arr2’ (second array) i.e. ‘arr2[0]’. For example, if arr1 is [ 1, 2, 4 ] and arr2 is [3, 4, 6 ], for each element in arr1 i.e. arr1[i] will give minimum sum with arr2[0] so the pair (x, y) such that ‘x’ is 1 and (‘x’ + ‘y’) is minimum will be (1, 3), same when ‘x’ is 2 the pair will be (2, 3) and when ‘x’ is 4 the pair will be (4, 3). Now the idea is to store all these pairs into a min-heap data structure up to ‘K’ pairs as we need only ‘K’ pairs. Now here we can see that the current heap doesn’t contain pairs with an overall minimum sum as pair (4, 3) gives sum 7 and pair (2, 4) gives sum 6 but it is not inserted in the heap. So when we pop a minimum sum pair (x, y) from the heap, we need to add the next minimum sum pair with ‘x’. For example, when we pop (1, 3) from the heap, we add (1, 4) in the heap as pair (1, 4) is the next minimum sum pair with ‘1’ as an ‘x’. Similarly, when we pop (2, 3), we add (2, 4) into the heap and now we get (2, 4) before (4, 3) in the min-heap. If we need ‘K’ pairs then we do a similar pop operation up to ‘K’ times and get ‘K’ pairs with the smallest sum.

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 { arr1[x] + arr2[y], (x, y) }, where ‘x’ and ‘y’ are the index of first and second values in a pair.
• Declare a min-heap of tuples say ‘allPairs’ to store pairs. The ordering of mi-heap is according to the first element of tuples, i.e. sum of pairs.
• Declare a list say ‘answer’ to store ‘K’ pairs with the smallest sum.
• Run a loop until minimum (size of arr1, ‘K’)
  • Push { arr1[i] + arr2[0], (i , 0) } into the heap, as we are storing the minimum possible pair with each element of ‘arr1’.
• Run a loop ‘K’ times
  • Pop a minimum element from the heap and store it in say ‘currPair’.
  • Add ‘currPair’ in the answer.
  • Push the next possible pair into a heap i.e let say ‘currPair’ is a pair with index (i, j) then the next possible pair will be pair with index (i, j + 1). So,
  • If  j + 1 < size of ‘arr2’, push { arr1[i] + arr2[j], (i, j + 1) }.
• Return ‘answer’.