Find n + m-1 unique pairs of sums for two arrays.



Example :

  Input:  N = 5, M = 3 A = [6, 5, 7, 1, 3] B = [2, 4, 8]  Output:  2 0 2 1 2 2 3 0 4 0 1 0 0 0 We have to form 5 + 3 - 1 = 7 pairs. These pairs are: (7, 2), (7, 4), (7, 8), (1, 2), (3, 2), (5, 2), (6, 2) All have unique sum  

Brute force approach: we can run a loop on both arrays A and B to find the first N + M-1 pairs of unique sums and print their indices along the way. 
To check if a specific amount has been used, we create a Python Bool dictionary. If the dictionary value for this sum is False, it means that this is the new sum value. If true, the amount has already been used.

Code :

from collections import defaultdict as dd

 
# Function for generating unique pairs of sums

def unique_pairs ():

 

  # Python Bool Dictionary

  d = dd ( bool )

ct = 0

 

  # For each element A, Find

# unique sum of a pair in B. Break

# loop after N + M-1 pairs

for i in range (n):

for j in range (m):

if (ct = = n   + m - 1 ):

break

sm = a [i] + b [j]

if (d [sm] = = False ):

d [sm] = True

ct + = 1

  print (i, j)

  

n, m = 6 , 4

a = [ 6 , 4 , 3 , 5 , 8 , 2 ]

b = [ 3 , 5 , 4 , 2 ]

 
unique_pairs ()

Output:

 0 0 0 1 0 2 0 3 1 0 1 3 2 3 4 1 4 2 

Time complexity: because we traverse the array using nested loops, the time complexity turns out to be O ().

Efficient approach: how only we will sort both arrays, first we can create N pairs of unique sums by connecting all elements of array A with the first element of array B, and then connecting the rest M — 1 elements of array B with the last element of array A.

Code :

from collections import defaultdict as dd

 
# Function for generating unique pairs of sums

def unique_pairs_sort ():

 

# Python Int Dictionary

da = dd ( int )

db = dd ( int )

 

# Make a dictionary to store the index

for i in range (n):

  da [a [i]] = i

for i in range (m):

db [b [i]] = i

 < / code> 

# Sort arrays

  a.sort (); b.sort ()

 

# N pairs A with B [0]

for i in range (n):

print ( da [a [i]], db [b [ 0 ]])

 

# M-1 pairs B with A [N-1]

for i in range ( 1 , m):

  print (da [a [ - 1 ]], db [b [i]])

  

n, m = 6 , 4

a = [ 6 , 4 , 3 , 5 , 8 , 2 ]

b = [ 3 , 5 , 4 , 2 ]

 
unique_pairs_sort ()

Exit:

 5 3 2 3 1 3 3 3 0 3 4 3 4 0 4 2 4 1 

Time complexity: The complexity for this is equal to the time it takes to sort: O (n Log n). 
Space complexity: because we are using two different maps / dictionaries to store array indices. The time complexity will be O (n + m), where n — the size of the first array, and m — the size of the second array.