Two Sorted Arrays, Sum Of 2 Elements Equal A Certain Number

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 num

Solution 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.

Solution 2:

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

defcheck_array(x, y, needed_sum):
    y = set(y)
    returnnext(((i, needed_sum-i) for i in x if (needed_sum-i) in y), None)