Two Sorted Arrays, sum of 2 elements equal a certa

Question

I was wondering if I could get some help. I want to find an algorithm that is THETA(n) or linear time for determining whether 2 numbers in a 2 sorted arrays add up to a certain number.

For instance, let's say we have 2 sorted arrays: X and Y

I want to determine if there's an element of X and an element of Y that add up to exactly a certain number, let's say 50.

I have been able to come up with these algorithms in Python so far, but I am pretty sure they are order of THETA(n^2) rather than THETA(n).

def arrayTestOne(X,Y):
    S =[1 for x in X for y in Y if x+y == 50]

def arrayTestTwo(X,Y):
    for x in X:
        for y in Y:
            if x + y == 50:
                print("1")

I'm thinking it's the double for loops that break the linear time, but how else would you iterate through 2 lists? Any thoughts would be appreciated.

Answer 1

What you can do is start with the highest in one list and the lowest in the other, and check the sum.

If the sum is your target, you're done.

If it's too high, go to the next highest value in the first list.

If it's too low, go to the next lowest value in the second.

If you go through both lists without reaching the target, you return false.

Answer 2

Here is a 2n for you which doesn't even need sorting:

def check_array(x, y, needed_sum):
    y = set(y)
    return next(((i, needed_sum-i) for i in x if (needed_sum-i) in y), None)