2
\$\begingroup\$

I'm solving the classic problem of finding two numbers from an array that sum to a given value.

Can anybody please check whether my analysis of time and space complexity is correct on this one?

# O(n) time | O(1) space 
def twoNumberSum(array, targetSum):
    for x in array:
        y = targetSum - x
        if y!=x and y in array:
            return [x, y]
    
    return []
\$\endgroup\$
4
  • 2
    \$\begingroup\$ It is nearly impossible to solve this problem with O(n) time and O(1) space. \$\endgroup\$ Commented Aug 10, 2021 at 6:26
  • \$\begingroup\$ Executing y in array already takes linear (O(n)) time. This is inside the for x in array loop, so this O(n) has to be multiplied by n (the number of elements you loop over). Hence quadratic (O(n²)) time, not linear. Also note y != x has nothing to do with the problem and should be removed for the code to give correct results, leaving only if y in array: \$\endgroup\$
    – Stef
    Commented Aug 10, 2021 at 14:51
  • 2
    \$\begingroup\$ I think the y!=x should actually be checking indices. As things are, twoNumberSum([2,2],4) will be false. If you remove it as Stef suggests, twoNumberSum([1,2],4) will be true. \$\endgroup\$
    – Teepeemm
    Commented Aug 10, 2021 at 15:04
  • \$\begingroup\$ @leaf_yakitori If the list is sorted, we can solve it with two pointers approach in linear time. \$\endgroup\$
    – Ch3steR
    Commented Aug 11, 2021 at 4:00

1 Answer 1

5
\$\begingroup\$

This code fails given [0, 1, 1] and 2 as inputs: it should return [1,1] but fails because the two numbers are identical. So it fails review, without any further analysis.

Scaling is poorer than you believe, if array is a list, since in is generally linear in the list length. Since in is used inside the for loop, time taken is proportional to O(n²).

When no result is present, I would probably choose to return None rather than an empty list.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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