How to quickly find sum of all pairs of elements in 2 different arrays

Question

So recently I hit upon this programming problem which I couldn't seem to make the complexity less (my current code runs in O(n^2)).

Essentially, I have four different lists (I'm using python btw) of integers, both positive and negative, say lists A, B, C, D. Now, each of these lists has 1000 integers, and these integers range from -25000 to 25000 inclusive. Now, suppose from each of these lists we choose an integer, say a, b, c, d. I would like the quickest way to find these a, b, c, d such that a+b=-(c+d).

Currently, my method relies on iterating through every single possible combination of a, b, and c, d, before then trying to find if an element in the set (a+b) exists in the set -(c+d). This, of course, is impractical since it runs in O(n^2) time, even more so considering the large list sizes (1000).

Hence I was wondering if anyone could think of a more efficient way (preferably O(n log n) or smaller), coded in python if possible.

Apologies if it's rather confusing. If you have any questions please inform me, I'll try to provide more clarification.

EDIT:

This problem is part of a larger problem. The larger problem states that if we have 4 sequences of numbers with at most 1000 integers in each, say A, B, C, D, find an a, b, c, d such that a+b+c+d=0.

I asked the above question since a+b+c+d=0 implies that a+b=-(c+d), which I thought would lead to the fastest way to solve the problem. If anyone can think of an even faster way, please do share it with me.

Thanks in advance! :)

Answer 1

Your problem isn't that combining pairs of elements is O(n^2), but rather the fact that you're combining two such processes naively to end up with an O(n^4) algorithm. I'm going to assume you just need to find >= 1 ways to add up to 0 -- my method given below can easily be extended to find all ways, if it's required.

Given that you have a relatively narrow range of accepted values (-25k to +25k, let's call those MIN and MAX respectively), here's what you do:

Create 2 int arrays of size (MAX - MIN + 1), "indicesA" and "indicesB". That's not even 0.5 MB of memory all together, so nothing to worry about on a modern system.

Now loop on all elements of lists A and B, just like you were doing. Do something like this pseudo-code (not too familiar with python so I'm not sure if it's valid as-is):

for idxA, valA in enumerate(A):
    for idxB, valB in enumerate(B):
        indicesA[valA + valB - MIN] = idxA + 1
        indicesB[valA + valB - MIN] = idxB + 1

Now just use this as an O(1) lookup-table when looping on B and C:

for valC in C:
    for valD in D:
        neededVal = -(valC + valD) - MIN
        if indicesA[neededVal] > 0:
            print('Found solution: {0} {1} {2} {3}'.format(A[indicesA[neededVal] - 1], 
                 B[indicesB[neededVal] - 1], valC, valD))

• Lookup-table initialization with 0s: O(MAX - MIN) (~50k, smaller than n^2 in this case)
• Filling lookup-table by looping on A and B: O(n^2)
• Looping on C and D and checking for any solutions: O(n^2)

Overall, O(n^2 + (MAX - MIN)) =~ O(n^2) with the values given. Probably can't do much better than that.