Find k pairs with smallest sums in two arrays | Set 2 | Function to print the K smallest pairs ; if k is greater than total pairs ; _pair _one keeps track of ' first ' in a1 and ' second ' in a2 in _two , _two [ 0 ] keeps track of element in the a2and _two [ 1 ] in a1 [ ] ; Repeat the above process till all K pairs are printed ; when both the pointers are pointing to the same elements ( po3 ) ; updates according to step 1 ; if ( _one [ 1 ] == 0 ) : see po2 ; updates opposite to step 1 ; updates according to rule 1 ; if ( _one [ 0 ] == 0 ) : see po2 ; updates opposite to rule 1 ; if ( _two [ 0 ] == 0 ) : see po2 ; else update as necessary ( po1 ) ; updating according to rule 1 ; if ( _one [ 1 ] == 0 ) : see po2 ; updating according to rule 1 ; if ( _one [ 0 ] == 0 ) : see po2 ; updating according to rule 1 ; if ( _two [ 0 ] == 0 ) : see po2 ; updating according to rule 1 ; if ( _two [ 1 ] == 0 ) : see po2 ; Driver Code
def printKPairs ( a1 , a , size1 , size2 , k ) : NEW_LINE INDENT if ( k > ( size2 * size1 ) ) : NEW_LINE INDENT print ( " k pairs don ' t exist " ) NEW_LINE return NEW_LINE DEDENT _one , _two = [ 0 , 0 ] , [ 0 , 0 ] NEW_LINE cnt = 0 NEW_LINE while ( cnt < k ) : NEW_LINE INDENT if ( _one [ 0 ] == _two [ 1 ] and _two [ 0 ] == _one [ 1 ] ) : NEW_LINE INDENT if ( a1 [ _one [ 0 ] ] < a2 [ _one [ 1 ] ] ) : NEW_LINE INDENT print ( " [ " , a1 [ _one [ 0 ] ] , " , ▁ " , a2 [ _one [ 1 ] ] , " ] ▁ " , end = " ▁ " ) NEW_LINE _one [ 1 ] = ( _one [ 1 ] + 1 ) % size2 NEW_LINE INDENT _one [ 0 ] = ( _one [ 0 ] + 1 ) % size1 NEW_LINE DEDENT _two [ 1 ] = ( _two [ 1 ] + 1 ) % size2 NEW_LINE if ( _two [ 1 ] == 0 ) : NEW_LINE INDENT _two [ 0 ] = ( _two [ 0 ] + 1 ) % size2 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( " [ " , a2 [ _one [ 1 ] ] , " , ▁ " , a1 [ _one [ 0 ] ] , " ] ▁ " , end = " ▁ " ) NEW_LINE _one [ 0 ] = ( _one [ 0 ] + 1 ) % size1 NEW_LINE INDENT _one [ 1 ] = ( _one [ 1 ] + 1 ) % size2 NEW_LINE DEDENT _two [ 0 ] = ( _two [ 0 ] + 1 ) % size2 NEW_LINE INDENT _two [ 1 ] = ( _two [ 1 ] + 1 ) % size1 NEW_LINE DEDENT DEDENT DEDENT elif ( a1 [ _one [ 0 ] ] + a2 [ _one [ 1 ] ] <= a2 [ _two [ 0 ] ] + a1 [ _two [ 1 ] ] ) : NEW_LINE INDENT if ( a1 [ _one [ 0 ] ] < a2 [ _one [ 1 ] ] ) : NEW_LINE INDENT print ( " [ " , a1 [ _one [ 0 ] ] , " , ▁ " , a2 [ _one [ 1 ] ] , " ] ▁ " , end = " ▁ " ) NEW_LINE _one [ 1 ] = ( ( _one [ 1 ] + 1 ) % size2 ) NEW_LINE INDENT _one [ 0 ] = ( _one [ 0 ] + 1 ) % size1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( " [ " , a2 [ _one [ 1 ] ] , " , ▁ " , a1 [ _one [ 0 ] ] , " ] ▁ " , end = " ▁ " ) NEW_LINE _one [ 0 ] = ( ( _one [ 0 ] + 1 ) % size1 ) NEW_LINE INDENT _one [ 1 ] = ( _one [ 1 ] + 1 ) % size2 NEW_LINE DEDENT DEDENT DEDENT elif ( a1 [ _one [ 0 ] ] + a2 [ _one [ 1 ] ] > a2 [ _two [ 0 ] ] + a1 [ _two [ 1 ] ] ) : NEW_LINE INDENT if ( a2 [ _two [ 0 ] ] < a1 [ _two [ 1 ] ] ) : NEW_LINE INDENT print ( " [ " , a2 [ _two [ 0 ] ] , " , ▁ " , a1 [ _two [ 1 ] ] , " ] ▁ " , end = " ▁ " ) NEW_LINE _two [ 0 ] = ( ( _two [ 0 ] + 1 ) % size2 ) NEW_LINE INDENT _two [ 1 ] = ( _two [ 1 ] + 1 ) % size1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT print ( " [ " , a1 [ _two [ 1 ] ] , " , ▁ " , a2 [ _two [ 0 ] ] , " ] ▁ " , end = " ▁ " ) NEW_LINE _two [ 1 ] = ( ( _two [ 1 ] + 1 ) % size1 ) NEW_LINE INDENT _two [ 0 ] = ( _two [ 0 ] + 1 ) % size1 NEW_LINE DEDENT DEDENT DEDENT cnt += 1 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a1 = [ 2 , 3 , 4 ] NEW_LINE a2 = [ 1 , 6 , 5 , 8 ] NEW_LINE size1 = len ( a1 ) NEW_LINE size2 = len ( a2 ) NEW_LINE k = 4 NEW_LINE printKPairs ( a1 , a2 , size1 , size2 , k ) NEW_LINE DEDENT