CODEWITHSUNDEEP
pythonarraysalgorithmbig-o
Russell Ng
Russell Ng

Reputation: 173

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

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! :)

Upvotes: 6

Views: 2285

Answers (2)

kaya3
kaya3

Reputation: 51034

You have four arrays and you want to choose one number from each array, such that the sum of the four numbers is zero. The technical name for this problem is 4SUM×4.

This problem is at least as hard 3SUM×3, where three numbers summing to zero must be chosen from three arrays. An instance of 3SUM×3 can be converted to an instance of 4SUM×4 by simply adding an array of zeros. So any algorithm solving your problem can be used to solve 3SUM×3 in the same time complexity.

It doesn't appear to be known for certain that 3SUM×3 isn't easier than the more famous 3SUM problem, but it seems very likely to be equally difficult. A 3SUM×3 algorithm can be used to solve the 3SUM problem or determine with arbitrarily high probability that no solution exists. (The only issue with reducing 3SUM to 3SUM×3 is that 3SUM×3 allows solutions like 1, 1, -2 whereas 3SUM doesn't.) The theoretically-best known algorithms for 3SUM only beat O(n2) by factors of (log n) to some power.

Given all of that, it seems very unlikely that your problem can be solved in significantly less than O(n2) time, asymptotically.

Upvotes: 0

tohoho
tohoho

Reputation: 349

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.

Upvotes: 1

Related Questions