Two sum with two lists

Question

Suppose we have two sorted lists, and we want to find one element from the first, and the other element from the 2nd list, where the sum of the two elements equal to a given target. If there are multiple combinations, need to find all the combinations.

Any bugs, performance improvement ideas in terms of algorithm time complexity or code style advice is highly appreciated. My basic idea is to scan the first list from the beginning, and scan the second list from the end, a similar approach to how we resolve the 2-sum classic problem in one list.

def two_sum(list1, list2, target, result):
    i = 0
    j = len(list2) - 1
    while i < len(list1) and j >= 0:
        if list1[i] + list2[j] == target:
            result.append((list1[i], list2[j]))
            i += 1
            j -= 1
            while i < len(list1) and list1[i] == list1[i-1]:
                i += 1
            while j >= 0 and list2[j] == list2[j+1]:
                j -= 1
        elif list1[i] + list2[j] > target:
            j -= 1
        else:
            i += 1
if __name__ == "__main__":
    list1 = [1,3,5,7]
    list2 = [2,3,4,5]
    result = []
    two_sum(list1, list2, 6, result)
    print result

Answer 1

Assuming that your lists are sorted and this is something that comes out of problem description and the part where you need to find something in 99% of that kind of questions you want to use binary search. So basically all your code could be written like this:

from bisect import bisect_left


def binary_search(a, x):
    pos = bisect_left(a, x)
    return pos if pos != len(a) and a[pos] == x else -1


def two_sum(a, b, target):
    result = []
    for num in a:
        index = binary_search(b, target-num)
        if index != -1:
            result.append((num, b[index]))
    return result

Now if you want to save some memory, you might want to make two_sum a generator, which will make it look like this:

def two_sum(a, b, target):
    result = []
    for num in a:
        index = binary_search(b, target-num)
        if index != -1:
            yield num, b[index]

I cannot really call my answer a review to your code because I completely overwrote a solution for this. But as I mentioned in the beginning whenever a problem says something about sorted lists and searching on it, most likely you will use bsearch in your solution.

Answer 2

I re-constructed your algorithm using generators, which I find easier on the eyes (instead of indexing) for these sort of list traversals. Other than that, the code is the same.

def two_sum(list1, list2, target):
    # Get a generator for each list
    l1 = iter(list1)
    l2 = reversed(list2)

    # loop and append to results list
    result = []
    try:
        # get the first sample from each list
        x = next(l1)
        y = next(l2)
        while True:

            # If we find a match, record it
            if x + y == target:
                new_pair = x, y
                result.append(new_pair)

                # get next unique elements
                x = next(l1)
                while x == new_pair[0]:
                    x = l1.next()

                y = next(l2)
                while y == new_pair[1]:
                    y = next(l2)

            # if no match, then get new element from one list
            elif x + y > target:
                y = next(l2)
            else:
                x = next(l1)

    # when one of the generators runs out of elements it will assert
    except StopIteration:
        pass
    return result


print(two_sum([1, 3, 5, 7], [2, 3, 3, 5], 6))

Answer 3

Hah, Alex was faster with the binary search version :) I submit my version because we can exploit the fact both lists are ordered, so you should use a second bsearch moreover you don't have to do binary search over the whole set, we can use the upper subset.

If the lists are large enough, this algorithm supposed to be much faster.

Please forgive me the C-ish code, I don't know python, I've just tried to find out the syntax from your code. :) Maybe you can Pythonize it. (Yes, that's why I implemented my binary search, I don't know the libs )

Especially I couldn't find an effective way for handle sublists. I think list[from:to] would memcpy the data which is a huge burden (maybe I'm not right). This way I had to simulate C pointers in the following code.

# find the greatest index of element 
# list where element is not greater than target
def bsearch(l, target, s, e):
    m = int((s+e)/2)
    if l[m] == target or e == m or s == m :
        return m
    if l[m] > target :
        return bsearch(l,target,s,m)
    return bsearch(l,target,m,e)

def two_sum(l1,l2,target):

    l2 = [target-x for x in  reversed(l2)]
    b2 = 0
    b1 = 0
    t = l1[0]
    res = []

    while True:
        b2 = bsearch(l2, t, b2 ,len(l2)-1)
        if l2[b2] == t :
            res.append((t,target-t))
        b2 += 1
        if b2 >= len(l2): return res
        t = l2[b2]

        b1 = bsearch(l1, t, b1 ,len(l1)-1)
        if l1[b1] == t :
            res.append((target-t,t))
        b1 += 1
        if b1 >= len(l1): return res
        t = l1[b1]

l1=[1,3,6,7,10,18,19,22,28,30]
l2=[5,8,9,11,18,19,21,32,34]
print(two_sum(l1,l2,26))

---

Alternatively:

def two_sum(A,B,target):

    L = B = [target-x for x in  reversed(B)]
    u = 0     # list pointers
    p = [0,0]
    resA = [] # results
    res = resB = []
    t = A[0]

    while True:
        print (L, u,':', p[u], t, resA, resB)
        p[u] = bsearch(L, t, p[u] ,len(L)-1)
        if L[p[u]] == t :
            res.append(t)
        p[u] += 1
        if p[u] >= len(L): 
            return [(target-x,x) for x in resA] + [(x,target-x) for x in resB]
        t = L[p[u]]
        # swap everything
        res = resA if res==resB else resB
        L = A if L==B else B
        u = 0 if u==1 else 1

However, in lack of real pointers it's a bit messy. I had to use the form p[u] instead of the clean p, because integers seems to be immutable in python. Of course len() should be factored out from the loop, it's just for simplicity.

Answer 4

Dictionary lookups in Python are usually \$O(1)\$ and going through a list once is \$O(n)\$, so I would do something like this:

def two_sum(list1, list2, target, result):
    results = []
    list2_dict = {n:1 for n in list2}

    for num in list1:
        if (list2_dict.get(target-num, None) != None):
            results.append([num, target-num])

    return results