11
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ OK Hash set creation for a list of size n will be \$O(n)\$, but the check will only be \$O(1)\$ if the data distributes well over the hash buckets. If this is part of a challenge with python specified, expect at least one dataset with rigged data that gets you an \$O(n)\$ check. \$\endgroup\$ – David G. Feb 18 at 13:36
  • \$\begingroup\$ if python2 is possible, you may want to use xrange() instead of range(). \$\endgroup\$ – David G. Feb 18 at 14:27
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ @DavidG., ok, as the OP mentioned time complexity (citing), have you measured time performance on 2 input lists, how fast is it? \$\endgroup\$ – RomanPerekhrest Feb 17 at 13:20
  • \$\begingroup\$ @RomanPerekhrest I have not timed the code because I have not written a complete implementation. I have calculated time complexity. Note all the \$O(...)\$ in the text. And depending on the list sizes, his implementation may well be the fastest, just as bubble sort can easily be the fastest sort. \$\endgroup\$ – David G. Feb 17 at 23:35
7
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 7
    \$\begingroup\$ And the fact that you didn't cache set(tests) means this might be \$O(n^{2} m)\$ instead of \$O(n^{2} + m)\$, depending on if the compiler decides it can cache this for you. \$\endgroup\$ – David G. Feb 16 at 23:11
  • 5
    \$\begingroup\$ @DavidG. Code Review is about improving code quality. Knocking an answer because it's not improving complexity and is instead making code more Pythonic, is not a site I want to contribute. \$\endgroup\$ – Peilonrayz Feb 17 at 15:07
  • \$\begingroup\$ @Peilonrayz In David's defense, OP very clearly asks for an improvement to complexity: "Is there a way to make time complexity more efficient?" \$\endgroup\$ – AleksandrH Feb 17 at 17:08
  • 1
    \$\begingroup\$ @AleksandrH A core part of Code Review is "do you want any and all of your code reviewed". We allow specific questions, but by posting you allow a review of anything. \$\endgroup\$ – Peilonrayz Feb 17 at 17:15
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ No, I am saying that I have some problem like 'making a friend', and I have another problem like 'sharing my feelings', and let's say that I can work out a simple (i.e. not time complex) way to turn 'making a friend' into 'sharing my feelings' (presumably the process is I make a friend and then corner them in a room and tell them all the things that make me sad). Then since making a friend implies I can share my feelings, if I know that sharing my feelings is very hard, then making a friend must be very hard. In this analogy making a friend is OPs problem and sharing my feelings is 3SUM. \$\endgroup\$ – Countingstuff Feb 17 at 20:47
  • \$\begingroup\$ Sorry, I feel like I'm wasting your time. I posted my previous comment and decided it wouldn't result in a good outcome, so deleted it. But you read it too fast 😓‎ \$\endgroup\$ – Peilonrayz Feb 17 at 20:53
  • \$\begingroup\$ Nice analysis, and I agree, if \$n=m\$ then you can't do better than \$O(n^2)\$. On the other hand, if m is comparatively tiny, you can do fairly well. \$\endgroup\$ – David G. Feb 18 at 0:29
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

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.