Suppose we have two sorted arrays: *A* and *B* of size *n*.

We would like to know if there is such a pair of indexes *(i,j)* that *A[i] + B[j] = C*.

*C* is a given number.

What’s the best worst-case time complexity (Big Oh) of the algorithm to solve the problem?

Advertisements

Hm. At first sight it is O(n*log(n)). But probably I’m wrong and there is O(n) solution.

Nikolay: Yes, that’s the first solution that comes to mind:

for i in A:

search(C – A[i]) in B

But… ;)

it looks like you have to pass each array only once, but at the same time and in different directions.

so Nikolay was right, there is a O(n) solution :)

p.s. i wonder if html tags work here invisible text

nope, html tags don’t work here :)

Aram: You’re right. There is O(n) solution :)

There is an obvious O(n) solution if you have infinite memory and numbers are integers :)

Damn!!! Arrays are sorted!!!!

That is really obvious then!!!

Actually, the merge sort algorithm exploits the same idea. Its ‘merge’ part takes an input of several sorted arrays and must choose, on which of them to step forward.

In this puzzle the tricky part is to process one of the arrays in the reversed order.

Here’s the puzzle from the same domain: “You have three sorted arrays and required to find a triplet of elements from each array having the minimum distance between them. Distance is calculated as max(|a[i] – b[j]|, |a[i] – c[k]|, |b[j] – c[k]|). The algorithm must have linear time complexity and constant space complexity”.