4 sum challenge (part 2)

Question

This is a continued discussion from (4 sum challenge) by return count only.

Problem

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where \0ドル \le N \le 500\$. All integers are in the range of \$-2^{28}\$ to \2ドル^{28} - 1\$ and the result is guaranteed to be at most \2ドル^{31} - 1\$.

Example:

Input:

A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:

2

Explanation:

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

I'm wondering if there are any ideas to have a solution less than \$O(n^2)\$ time complexity.

Source code in Python 2.7,

from collections import defaultdict
def four_sum(A, B, C, D):
 sum_map = defaultdict(int)
 result = 0
 for i in A:
 for j in B:
 sum_map[i+j] += 1
 for i in C:
 for j in D:
 if -(i+j) in sum_map:
 result += sum_map[-(i+j)]
 return result
if __name__ == "__main__":
 A = [1, 2]
 B = [-2, -1]
 C = [-1, 2]
 D = [0, 2]
 print four_sum(A,B,C,D)

• greybeard: Doubts rather than ideas about ο(n²). I might establish the extrema (& medians?) of the lists, combine for smallest ranges/least (expected) overlap and leave out sums from the sum2count map that can't be neutralised. (If the sum2count map was navigable as well as the remaining lists, it might be possible to cut down search time without drawing on expected constant time membership queries.)
• Raziman T V: That looks good. Does calling map[x] on a non existing element in python automatically set it to zero instead of giving an error?
• Lin Ma: @greybeard, totally agree your strategy could optimize search time, but I think it is still O(n^2), if I mis-read your comments, appreciate if you could show your idea by code, which is less time complexity than O(n^2). :)
• Lin Ma: @RazimanT.V., it is the power of defaultdict, which makes it more elegant without checking a key exists. BTW, do you have any ideas which time complexity less than O(n^2)?
• Raziman T V: @LinMa No, I don't think it is possible to do better than O(n^2).

Answer 1

Proof that it cannot be done (at least based on our current understanding) in much better than \$O(n^2)\$:

Suppose A = B = C and D is a list of zeros. Then the problem reduces to finding three numbers in A that sum to zero. This is the famous 3SUM problem, for which we do not have a "much" better general solution than \$O(n^2)\$.

• Lin Ma: Thanks Raziman, love your prove and vote up. But I am not sure you prove for a special case or general case? Or your general idea is the specific 4 sum problem cannot be faster than 3 sum problem -- where the best of 3 sum problem time complexity is O(n^2)?
• Raziman T V: If the general solution to the 4-sum was faster, you could reduce 3-sum to 4-sum as I did here. Since 3-sum has no known "much" faster solution, that proves that 4-sum cannot be faster as well.

Answer 2

I’m not sure I can get it any better than \$O(n^2)\,ドル but I would point you towards the itertools module as a way to tidy up your code by reducing the number of nested for loops. Like so:

def four_sum(A, B, C, D):
 sums = defaultdict(int)
 result = 0
 for (a, b) in itertools.product(A, B):
 sums[a + b] += 1
 for (c, d) in itertools.product(C, D):
 result += sums[-(c + d)]
 return result

I’ve also tweaked the names of some of the variables to make the code easier to follow, and changed it so it only has to compute (c+d) once.

• greybeard: result += sums[-c-d] [will add the default] 0 if s not in sum, should be faster for one less lookup in sums, two lines shorter and more symmetrical (oops - edited in). (Negating C & D en bloc before iterating their sums might save time, but look less convincing.)
• Graipher: Hehe, apparently not. Now you wrote sum instead of sums. Incidentally, the second for loop can be done as result = sum(sums[-(c + d)] for (c, d) in itertools.product(C, D) now.
• Lin Ma: Thanks alexwlchan, love your code and comments, and vote up. Wondering why do you think we cannot make it better than O(n^2)? Do you have some rough prove for lower bound to be O(n^2)?