Iteration

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.

$\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:

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)$. 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:

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:

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

Space Complexity $O(1)$.

Mark as Completed: