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

Question

I recently ran into this programming problem that apparently couldn't make the complexity less (my current code works in O (n ^ 2)).

In fact, I have four different lists (I use python btw) of integers, both positive and negative, for example, lists A, B, C, D. Now each of these lists has 1000 integers, and these integers from -25000 to 25000 inclusive. Now suppose that from each of these lists we select an integer, say, a, b, c, d. I would like the fastest way to find these a, b, c, d such that a + b = - (c + d).

My method currently relies on iterating through every possible combination of a, b, and c, d, before trying to find if an element in the set (a + b) exists in the set - (c + d). This, of course, is not practical, since it works O (n ^ 2) times, especially considering the large size of the list (1000).

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

Sorry if this is pretty confusing. If you have any questions, please let me know, I will try to give more clarification.

EDIT:

This problem is part of a larger problem. The big problem is that if we have 4 sequences of numbers with no more than 1000 integers, say A, B, C, D, find a, b, c, d such that a + b + c + d = 0.

I asked this question since a + b + c + d = 0 means that a + b = - (c + d), which I thought would lead to the quickest solution to the problem. If anyone can think of even faster ways, please share it with me.

Thanks in advance!:)

Answer 1

Your problem is not that combining pairs of elements is O (n ^ 2), but rather that you combine two such processes naively to complete the O (n ^ 4) algorithm. I assume that you just need to find a> = 1 way to add to 0 - my method below can be easily extended to find all the paths if necessary.

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

Create 2 internal size arrays (MAX - MIN + 1), "indexes A" and "indexes B". This is not even 0.5 MB of memory, so there is nothing to worry about in a modern system.

Now let's move on to all the elements of lists A and B, just like you did. Do something like this pseudocode (not too familiar with python, so I'm not sure if it is valid as it 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 your O (1) lookup table when looping to 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)) 

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

In general, O (n ^ 2 + (MAX - MIN)) = ~ O (n ^ 2) with the indicated values. It probably can't do much better.