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:

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

a + b = 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:

b = target - a\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:

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.

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

Space Complexity O(n)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:

Mark as Completed:
Test your code to get an output here!
Test your code to get an output here!