Are the sum of two numbers desired?

Question

Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add up to the any numbers in the second array.

\$-1 + 3 = 2 \therefore \text{True}\$

My algorithm simply takes all the pairs from the first input and check if they exist in second array set which the complexity of set lookup is \$O(1)\$. Overall complexity is \$O(n^2)\$ I'm pretty sure there should be a better algorithm leveraging hash tables or sorting and doing a binary search. Is there a way to make time complexity more efficient?

My code:

def arraySum(inputs, tests):
    # iterating through all possible sums and check if it exists in test by using a test set which 
    #makes the complexity better with O(1) lookup in set.
    my_set=set(tests)
    for i in range(len(inputs)-1):
        for j in range(i+1,len(inputs)):
            my_sum=inputs[i]+inputs[j]
            if my_sum in my_set:
                return True
    return False #this will take care of an edge case when there is one input from each arr

Answer 1

I believe you could reduce it to \$O(n\log{n}+m\log{n}+n m)\$ if you want.

Sort the inputs, then iterate over the tests and for each one, do a two variable iteration over the inputs, where you start as close to the test value/2, and move one index in the increasing direction and the other in the decreasing direction depending on whether the sum is less than or greater than the test value.

This is somewhat confusing, so a partial implementation is:

def one_test(sorted_array, test_value):

    index1 = index_just_under(sorted_array, test_value/2)
    index2 = index1 + 1

    while (index1>=0) and (index2 < len(sorted_array)):
        sum = sorted_array[index1] + sorted_array[index2];
        if sum == test_value:
            return True
        if sum > test_value:
            index1 = index1 - 1
        else:
            index2 = index2 + 1

    return False

Function index_just_under would be an \$O(\log{n})\$ method to find our initial cut point. It returns the number of entries in the array below the second parameter, minus 1. Given a sorted array, a binary search can be used.

The rest of this one_test function is \$O(n)\$. This function is executed \$m\$ times, and the initial sort is \$O(n\log{n})\$.

While this might be a poor savings of the two input arrays are the same size, if tests array is much smaller, this could be a big saving.

If you start the indexes at the 0 and len(sorted array) - 1, you might be able to eliminate the index_just_under() call, reducing the time by \$O(m\log{n})\$. On the other hand, it would eliminate any early-outs in the \$O(n m)\$ loops. Effectiveness could depend on your expected number ranges.

Answer 2

Your function code can be simplified to one line.

from itertools import combinations
from typing import List

def array_sum(inputs: List[int], tests: List[int]) -> bool:
    """
    Determines if any two integers in `inputs` 
    add up to any integer in `tests`.

    :param List[int] inputs: Input data
    :param List[int] tests: Numbers to test against input data

    :return bool: True if combination is found, False otherwise
    """
    return any(sum(pair) in set(tests) for pair in combinations(inputs, 2))

This uses docstrings to document what the function does, and what types the function accepts and returns.

The main meat of the function occurs in one line. any() returns True if any element in the given iterable is True. Converting tests to a set removes any duplicate values, possibly reducing the number of iterations. The combinations returns subsequences of the iterable. Because you want two numbers to add up to one number in the test set, the value 2 is passed to the function.

Answer 3

Instead of using nested for loops for your case - Python provides a more flexible and performant features with itertools module, suitably - itertools.combinations(iterable, r) which returns generator of r length subsequences of elements from the input iterable.

Besides, don't forget about good naming: arraySum is not a good one (at least array_sum). I'd suggest check_sum as alternative.

Optimized version:

import timeit
from itertools import combinations


def check_sum(input_lst, test_lst):
    search_set = set(test_lst)
    for pair in combinations(input_lst, 2):
        if (pair[0] + pair[1]) in search_set:
            return True
    return False


lst1 = [-1, 8, 3]
lst2 = [3, 7, 2]

---

Now, let's compare running time performance between arraySum and check_sum:

print(timeit.timeit('arraySum(lst1, lst2)', globals=globals(), number=1))
print(timeit.timeit('check_sum(lst1, lst2)', globals=globals(), number=1))

The output:

2.621993189677596e-06
1.6039994079619646e-06

Answer 4

Your problem is at least as hard as 3SUM, https://en.wikipedia.org/wiki/3SUM (in fact it is very likely equivalent with a little thought).

Let us first see how to reduce a 3SUM problem to your problem.

3SUM says I have an array \$X\$, and I want to find out if there are \$x\$, \$y\$, \$z\$ in \$X\$ such that $$x + y + z = 0$$

Let us define \$A = X\$ and \$B = [-a\ \$ for \$ a \$ in \$ A]\$

Then let us solve your problem, i.e. determine if there are \$x\$ and \$y\$ in \$A\$ such that \$x + y\$ is in \$B\$, that is, there is some \$z\$ in \$A\$ such that \$x + y = -z\$, then we have determined whether \$X\$ has \$x\$, \$y\$, \$z\$ such that \$x+y+z=0\$.

Ergo, suppose we can solve your problem in better than \$O(nm)\$ time (and not such that the case \$n=m\$ doesn't magically reduce to \$n^2\$) where \$|A| = n\$ and \$|B| = m\$

Then for a 3SUM problem we could reduce it to your problem and solve that, thus solving the 3SUM problem in better than \$O(n^2)\$ time (in this case \$n = m\$)

Given that it's a long standing conjecture whether you can do \$O(n^{2-e})\$ for some \$e > 0\$ for 3SUM I'm inclined to suggest you aren't going to find better than \$O(nm)\$, ignoring that as detailed in the wikipedia link above there are actually marginally better time complexities which have been achieved.

Answer 5

I think I overlooked the obvious. Without sorting, if you do the loops as:

def arraySum2(inputs, tests):
    my_set=set(inputs)
    for a in inputs:
        for b in tests:
            if (b-a) in my_set:
                return True
    return False

Then you get \$O(n m + n)\$

This will be faster than the original (or itertools based variants) around \$m<{{n-1}\over{2}}\$ as the original does \${n(n-1)}\over2\$ tests and this does \$n m\$.

If you are doing the test a lot, it is thus worth implementing both forms, with a test to decide which form to use.