[Python] 4SUM variation in quadratic complexity (Python 3.5)

I've been having a little bit of problem with a variation of the 4SUM problem. Essentially, we are required to choose one number, say i, j, k, l from 4 tuples of 500 integers each, say a, b, c, d, such that i+j+k+l == 0. These integers range from -20000 to 20000. Currently, my code has a time complexity of O(n3) I believe. According to my instructor, this time complexity can be reduced even further, to either O(n2 log n) or O(n2) (by using hash tables or something).

Unfortunately, if this hash tables method is the way to go, I am not sure how to go about implementing it. Hence if anyone could show me how to code this program in Python 3.5 I would be most grateful. (PS. please do try to use as few nested loops as possible, none would be ideal).

I have attached my code below for reference. If it is possible to modify my current code to reduce its time complexity, please do inform me as well.

import collections

import itertools


def selection(a, b, c, d):
"""program has 4 main parts,
firstly, triple_sum finds possible 3sums in the list abc
secondly, is_iterable ensures that inputs of tuple length 1 (ie. not iterable) are made iterable
thirdly, main function determines if there exists possible a, b, c in abc that correspond to each d
fourthly, main function checks if only 1 of the 3 integers from triple_sum exist in each array"""

'''use sort O(n log n) to sort input array, then find possible 3sums in O(n^2)'''
def triple_sum(a, res):
a.sort()
positions = collections.defaultdict(set)
for i, n in enumerate(a):
positions[n].add(i)
for (i, ai), (j, aj) in itertools.combinations(enumerate(a), 2):
n = res - ai - aj
if positions[n].difference((i, j)):
return n, ai, aj

'''Ensure that all inputs are iterable'''
def is_iterable(x):
if isinstance(x, collections.Iterable):
return x
else:
return x,

a, b, c, d = is_iterable(a), is_iterable(b), is_iterable(c), is_iterable(d)
abc = a + b + c
abc = [i for i in abc]

'''find value of d which has corresponding a, b, c
and returns appropriate value if conditions are met'''
ans_a, ans_b, ans_c, ans_d = 0, 0, 0, 0
for i in d:
x = 0 - i
j = triple_sum(abc, x)
if j[0] in a and j[1] in b and j[2] in c:
ans_a, ans_b, ans_c, ans_d = j[0], j[1], j[2], i
break
elif j[0] in a and j[2] in b and j[1] in c:
ans_a, ans_b, ans_c, ans_d = j[0], j[2], j[1], i
break
elif j[1] in a and j[0] in b and j[2] in c:
ans_a, ans_b, ans_c, ans_d = j[1], j[0], j[2], i
break
elif j[1] in a and j[2] in b and j[0] in c:
ans_a, ans_b, ans_c, ans_d = j[1], j[2], j[0], i
break
elif j[2] in a and j[0] in b and j[1] in c:
ans_a, ans_b, ans_c, ans_d = j[2], j[0], j[1], i
break
elif j[2] in a and j[1] in b and j[0] in c:
ans_a, ans_b, ans_c, ans_d = j[2], j[1], j[0], i
break
else:
continue

return ans_a, ans_b, ans_c, ans_d


Thanks in advance

PS. If anyone needs more clarification or information do let me know.

Continue reading...