algorithm - Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k

Question

I am looking for the solution of following algorithm with minimal time and space complexity.

Given two arrays a and b, find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k (any integer).

I was able to come up with O(n log n) approach where we will sort one of the array say A and for each of the element b in array B, do binary search on sorted array A for value (K-b) .

Can we improve it any further?

Answer 1

If the arrays are sorted you can do it in linear time and constant storage.

• Start with two pointers, one pointing at the smallest element of A, the other pointing to the largest element of B.
• Calculate the sum of the pointed to elements.
• If it is smaller than k increment the pointer into A so that it points to the next largest element.
• If it is larger than k decrement the pointer into B so that it points to the next smallest element.
• If it is exactly k you've found a pair. Move one of the pointers and keep going to find the next pair.

If the arrays are initially unsorted then you can first sort them then use the above algorithm. There a few different approaches for sorting them that you could use, depending on the type of data you expect:

• A comparison sort, e.g. Mergesort or Timsort.
• Counting sort.
• Radix sort.

A comparison sort will require O(n log n) time on average. The last two are faster than O(n log(n)) but can be impractical if the range of possible values in the input arrays is very large.