Find k pairs with smallest sums in two arrays | Python3 program to prints first k pairs with least sum from two arrays . ; Function to find k pairs with least sum such that one elemennt of a pair is from arr1 [ ] and other element is from arr2 [ ] ; Stores current index in arr2 [ ] for every element of arr1 [ ] . Initially all values are considered 0. Here current index is the index before which all elements are considered as part of output . ; Initialize current pair sum as infinite ; To pick next pair , traverse for all elements of arr1 [ ] , for every element , find corresponding current element in arr2 [ ] and pick minimum of all formed pairs . ; Check if current element of arr1 [ ] plus element of array2 to be used gives minimum sum ; Update index that gives minimum ; update minimum sum ; Driver code
import sys NEW_LINE def kSmallestPair ( arr1 , n1 , arr2 , n2 , k ) : NEW_LINE INDENT if ( k > n1 * n2 ) : NEW_LINE INDENT print ( " k ▁ pairs ▁ don ' t ▁ exist " ) NEW_LINE return NEW_LINE DEDENT index2 = [ 0 for i in range ( n1 ) ] NEW_LINE while ( k > 0 ) : NEW_LINE INDENT min_sum = sys . maxsize NEW_LINE min_index = 0 NEW_LINE for i1 in range ( 0 , n1 , 1 ) : NEW_LINE INDENT if ( index2 [ i1 ] < n2 and arr1 [ i1 ] + arr2 [ index2 [ i1 ] ] < min_sum ) : NEW_LINE INDENT min_index = i1 NEW_LINE min_sum = arr1 [ i1 ] + arr2 [ index2 [ i1 ] ] NEW_LINE DEDENT DEDENT print ( " ( " , arr1 [ min_index ] , " , " , arr2 [ index2 [ min_index ] ] , " ) " , end = " ▁ " ) NEW_LINE index2 [ min_index ] += 1 NEW_LINE k -= 1 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr1 = [ 1 , 3 , 11 ] NEW_LINE n1 = len ( arr1 ) NEW_LINE arr2 = [ 2 , 4 , 8 ] NEW_LINE n2 = len ( arr2 ) NEW_LINE k = 4 NEW_LINE kSmallestPair ( arr1 , n1 , arr2 , n2 , k ) NEW_LINE DEDENT