0

Suppose we have two Given unsorted arrays A and B ,finding some pair of elements (such that first element belongs to A and the second one belongs to B) whose sum (or difference?) equal to given k - by sorting only one of the arrays .

I wonder if there is an algorithm using good complexity for that. Any way, I habe tried to use that link 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 , but I found it unhelpful because I dont fond there any reference to a possible solution which uses sorting of only one sort.

DonaldT
  • 103
  • 8

3 Answers3

2

My solution, assuming there is no space restriction on the problem, assuming A has length n and B has length k:

-For each element a in array A (n iterations), store k-a, -k-a and k+a in a HashSet/some similar data structure that has a O(1) contains() function.

-Then, for each element b in array B (k iterations), check if b is in the Hashset/Map using the O(1) contains() function. If it is, we are done and return b and the corresponding a value such that a+b=k, a-b=k or b-a=k (I'm not sure whether or not you want to consider differences for this problem, that is up to you).

In summary, this algorithm operates in max O(n+k) time, with a space complexity of O(3n) (assume WLOG that n < k to maximize effectiveness). Both of these terms are linear, meaning that if a pair (a,b) exist to satisfy the problem, they will be found relatively quickly, and no sorting is necessary.

Hope this helps, sorry about the poor formatting (I wish SO had support for Latex, that would be nice for problems like these). Leave a comment/question if you need help understanding something I did because it may very well not be clear.

Alerra
  • 1,479
  • 11
  • 25
  • isnt there any option without using hash? – DonaldT Aug 30 '18 at 22:52
  • Using a normal list would cause the `contains()` to be on the order `n` so, giving O(n^2) for the total complexity. This still isn't terrible, but a Hashmap (or similarly effficient data structure) would be optimal. – Alerra Aug 30 '18 at 22:59
1

Since the problem requires to sort at least one of the array, it's impossible to have a better time complexity than O(n*log(n)).

A possible approach to this problem would be sort array A, and iterate over the array B. For every x belonging to B, binary search for the value (K - x) on A. If it exists, well, we've found our pair.

The overall runtime complexity for iterating over B is O(n) and for each binary search on A is O(log(n)), hence giving us the combined runtime complexity of O(n*log(n)) for finding our required pair.

We can use a in-place sorting algorithm like Quicksort if the array A is mutable to limit our space complexity to O(1).

Nilesh
  • 1,388
  • 6
  • 17
0

Is this what you are looking for?

Sort(A)
for( b : B)
  if A.Find(k-b)
    print k-b, b
Surt
  • 15,501
  • 3
  • 23
  • 39