Iteration

Two Sum

Given an array of numbers arr and a number target, return whether any 2 numbers in the array sum to the target.

The array will contain at least 2 elements.

First Few Test Cases:

twoSum([3, 3], 6)
# True

twoSum([1, 2, 3], 6)
# False

twoSum([1, 2, 3, 4], 6)
# True

To solve this problem, you have to check if two numbers in the array add to the target.

\notag \texttt{a + b = target}

To solve problems like this efficiently, you should always solve for one of the variables using the other variables. We can do this by subtracting a from both sides of the equation:

\notag \texttt{b = target - a}

This equation means that the value of b is completely determined by the values of a and target, because b = target - a. This means that you don't have to loop over b. Here's the code to solve the problem:

def twoSum(arr, target):

    for a in arr: # only loop over `a`

        b = target - a
        
        # if `b` exists in the array
        # then we know that `a + b = target`
        if b in arr:
            return True

    return False

This code is 99% there, but it's slightly broken - this code allows elements to be added with themselves. *

To fix this, you can make it so that b is always a different element from a. To do this, you can keep track of all the elements you've seen so far as you walk, and only search for b in all the previous elements you've seen. Here's a visual of this:

Here's the code for this. We're using a Set so that looking up elements is fast.

def twoSum(arr, target):

    numsSet = set([]) # a set of all the numbers we've seen

    for a in arr:
        
        b = target - a

        if b in numsSet: # lookup in a set, O(1)
            return True
        
        numsSet.add(a) # mark `a` as seen, O(1)

    return False

Time Complexity $O(n)$ . The for loop takes $O(n)$ time.

Space Complexity $O(n)$ . We have to store a set with all the numbers in it.

Here's the brute-force solution you might have started with, although it's suboptimal:

Open SpoilerClose Spoiler

To solve this problem, you could loop over all possible numbers a and b and check if they add to the target, but this is very inefficient. Here's the code:

def twoSum(arr, target):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)): # j greater than i

            # return True if numbers add to target
            if arr[i] + arr[j] == target:
                return True

    return False

Time Complexity $O(n^2)$ . We have a double for-loop, which takes $O(n^2)$ .

Space Complexity $O(1)$ .

Mark as Completed:

Submits:

twoSum

Test your code to get an output here!

twoSum(

)

Test your code to get an output here!