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

```