1

I would like to know what's the least time consuming algorithm for this.

Given 2 arrays, a and b, check if any 2 members - one from a and one from b add upto a given number h.

What do you think is the fastest algorithm for this problem? I'm simply looping over both the arrays and trying to find the solution which is very expensive. It's O(mn), I think, where m and n are the lengths of arrays a and b, respectively. Also, it's not necessary that both the arrays have the same length. Do you know any algorithm which is faster than this? For size, consider that the maximum length of both the arrays is about 100000.

Thanks.

P.S. This question isn't a duplicate as it concerns with finding the integers in two different arrays, not one.

TheRandomGuy
  • 327
  • 5
  • 20
  • 2
    Possible duplicate of [Find a pair of elements from an array whose sum equals a given number](http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number) – n. 1.8e9-where's-my-share m. May 06 '16 at 07:22
  • @n.m. That question is about finding them from a single array. In this question, two arrays have been given. They are very different cases. – TheRandomGuy May 06 '16 at 07:29
  • 1
    No, it is basically the same thing. Go through the first array, put each `array1[i]` into a hashtable. Then go through the second array, looking up `h - array2[i]` in the hashtable; if it exists, return `true`. – svinja May 06 '16 at 07:35
  • They are in fact very minor variations of the same thing. Not hard to replace `a[i]+a[j]` with `a[i]+b[j]` etc. – n. 1.8e9-where's-my-share m. May 06 '16 at 08:38
  • so no-one likes the odd/even method? – Christian Cerri May 06 '16 at 11:22

3 Answers3

3

You can sort one of the two arrays, say array b, then iterate through array a. For each element in a, use binary search to find an element in b that "matches", i.e. add upto h. Then the complexity will be O(n log n) for the sorting, plus O(m log n) for the iteration and binary search.

Codor
  • 17,235
  • 9
  • 32
  • 52
ycsun
  • 1,785
  • 1
  • 12
  • 20
  • Very nice answer; in fact, the _larger_ one of the arrays should be sorted and iterated in the inner loop via binary search, as the impact on running time will be larger. – Codor May 06 '16 at 07:22
2

As a heuristic improvement, the arrays can be sorted beforehand.

If n is nonnegative, sort the arrays A and B in non-increasing order. Suppose that the outer loop iterates the first array in this sorted order and the inner loop iterates the second array in this sorted order, considering summands a and b respectively. Iteration of the inner loop can be terminated as soon as a+b is smaller than n.

Likewise, if n is negative, the arrayscan be sorted in non-decreasing order; the inner loop can be terminated as soon as a+b is larger than n.

However, this does not reduce the worst-case time complexity, as in the worst case still every pair of numbers in the input will be checked.

Codor
  • 17,235
  • 9
  • 32
  • 52
  • 1
    (With one array sorted, you could check with a binary search for (the difference resulting from) each element of the other array.) – greybeard May 06 '16 at 07:18
  • @greybeard Indeed, seems as if the runnig time could be reduced to `O(n log n)`. – Codor May 06 '16 at 07:20
  • 3
    With both arrays sorted, you can just scan them in opposite directions. – n. 1.8e9-where's-my-share m. May 06 '16 at 07:25
  • @n.m. Could you explain how? – TheRandomGuy May 06 '16 at 07:39
  • 1
    @Dhruv Start with the smallest element of `a` and the largest element of `b`. If their sum is too large, step to the next largest element of `b`, otherwise step to the next smallest element of `a`. Continue until you achieve the required sum or step through the whole of `a` or `b` without finding a match. – r3mainer May 06 '16 at 07:58
0

You could use odd/even to approximately halve your time:

split a and b into 2 arrays each, resulting in aeven, aodd, beven, bodd. If n is even, compare (aeven + beven) and (aodd + bodd). If n is odd, compare (aeven + bodd) and (aodd + beven).

So, if |a|=20, and |b|=20 you would have 400 tests. If we assume approximately the same number of odd and evens in each array, |aeven| (and other sub arrays) will be approx 10, so you will have 10*10+10*10 tests, or approx 200.

Plus of course, order the arrays and stop testing for each value in the first array when the sum is greater than n.

Christian Cerri
  • 1,203
  • 2
  • 14
  • 19