Find equal pairs

Problem

Given an array A of unique integers, find the index of values that satisfy A + B =C + D, where A,B,C & D are integers values in the array. Find all combinations of quadruples.

I posted two versions of solutions and am wondering if there are any further smart ideas to make it run faster. I thought there might be some ideas which sort the list first, and leveraging sorting behavior, but I cannot figure out anything so far.

My code is $O(n^2)$ time complexity in the first version, where $n$ is the number of elements, and $O(s^2)$ in the second version, where $s$ is the max possible sum of elements.

from collections import defaultdict

def find_equal_pair1(numbers):
sum_map = defaultdict(list)
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
sum_map[i+j].append((numbers[i], numbers[j]))

result = []
for v in sum_map.values():
if len(v) > 1:
result.append(v)
return result

def find_equal_pair2(numbers):
sum_upper_bound = max(numbers) * 2 - 1
sum_lower_bonud = numbers[1] + numbers[2]
numbers_set = set(numbers) # to make look-up existence O(1)
sum_map = defaultdict(list)
for s in range(sum_lower_bonud, sum_upper_bound + 1):
for i in range(1, (s-1)//2 + 1):
if i in numbers_set and s-i in numbers_set:
sum_map[s].append((i, s-i))
result = []
for v in sum_map.values():
if len(v) > 1:
result.append(v)
return result

if __name__ == "__main__":
print find_equal_pair1([1,2,3,4])
print find_equal_pair2([1,2,3,4])

• Tried golfing it? – TrojanByAccident Jan 10 '17 at 10:25
• @TrojanByAccident, what do you mean? More details? – Lin Ma Jan 11 '17 at 3:51
• "...wondering if there are any further smart ideas to make it run faster..." codegolfing it would make it faster, simply because of less code – TrojanByAccident Jan 11 '17 at 3:57
• I have the feeling that, in the first version, sum_map[i+j].append((numbers[i], numbers[j])) should be sum_map[numbers[i]+numbers[j]].append((i, j)). Or am I missing something? – 409_Conflict Jan 11 '17 at 20:54
• I mean making the code as short as possible. – TrojanByAccident Jan 12 '17 at 1:09

Problem analysis

Since we know that each element in numbers is unique, we are guaranteed that $s \gt n$. So I wouldn't choose the second solution. It's even more obvious using numbers = [1, 2, 10000, 10001] where $10002 = 10000 + 2 = 10001 + 1$ will be found quickly by the first version but will take a long time with the second one.

Let's focus on the first version, then.

Bug

First off, you swapped storage position for the sum of 2 elements and their indexes:

sum_map[i+j].append((numbers[i], numbers[j]))


Should be:

sum_map[numbers[i]+numbers[j]].append((i, j))


Next, the exercise ask for every combination of quadruplets but you are returning a list of couples. Meaning that you will have to kind of repeat the logic to perform combinations.

Combinations

Whenever you need unique combinations of $n$ elements from an iterable, instead of using $n$ for loops on indexes, use itertools.combinations. It is both cleaner and faster (since it is implemented in C). It also easily handle cases where the iterable length is less than $n$.

Here you also need the indexes, so I suggest the following rewrite using enumerate:

from collections import defaultdict
from itertools import combinations

def find_equal_pair(numbers):
sum_map = defaultdict(list)
for (index1, element1), (index2, element2) in combinations(enumerate(numbers), 2):
sum_map[element1+element2].append((index1, index2))

result = []
for v in sum_map.values():
for (a, b), (c, d) in combinations(v, 2):
result.append((a, b, c, d))
return result


You can also turn the results formatting into a listcomprehension:

    return [
(a, b, c, d)
for values in sum_map.values()
for (a, b), (c, d) in combinations(values, 2)
]

• Thanks Mathias, love your comments, but your algorithm time complexity is still O(n^2), do you have any ideas which time complexity less than O(n^2)? Not sure if sorting could help? – Lin Ma Jan 13 '17 at 6:40
• @LinMa Yes I didn't try to provide an algorithm with better complexity because I don't have one at hand. Computing the indexes of a quadruplet whose sums are equal to a target number can be done in O(n). However, we don't have a target sum and must figure out each combinations of indexes for each possible target sum, hence O(n2). – 409_Conflict Jan 13 '17 at 8:04
• Sure Mathias, do you think my problem could be transferred to 23 sum problem? cs.stackexchange.com/questions/2973/… – Lin Ma Jan 14 '17 at 4:10