5
\$\begingroup\$

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])
\$\endgroup\$
  • 1
    \$\begingroup\$ Tried golfing it? \$\endgroup\$ – TrojanByAccident Jan 10 '17 at 10:25
  • \$\begingroup\$ @TrojanByAccident, what do you mean? More details? \$\endgroup\$ – Lin Ma Jan 11 '17 at 3:51
  • 1
    \$\begingroup\$ "...wondering if there are any further smart ideas to make it run faster..." codegolfing it would make it faster, simply because of less code \$\endgroup\$ – TrojanByAccident Jan 11 '17 at 3:57
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – 409_Conflict Jan 11 '17 at 20:54
  • 1
    \$\begingroup\$ I mean making the code as short as possible. \$\endgroup\$ – TrojanByAccident Jan 12 '17 at 1:09
4
\$\begingroup\$

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)
    ]
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Lin Ma Jan 13 '17 at 6:40
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – 409_Conflict Jan 13 '17 at 8:04
  • \$\begingroup\$ Sure Mathias, do you think my problem could be transferred to 23 sum problem? cs.stackexchange.com/questions/2973/… \$\endgroup\$ – Lin Ma Jan 14 '17 at 4:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.