Two Sum

Problem

Given an array of numbers, return every pair of numbers that can be added up to a given target.

Example:

Input: sum = 6, array = [5, -2, 4, 9, 1]

Output: [ [5, 1] ]

There are a few common ways of solving this problem, and I’d like to review each of them in totality.

Brute Force

With brute force, we try every possible combination of numbers and aren’t particularly worried about runtime. It’s important to first just get a working solution and then optimize.

First we must set an empty array that we can later store our answers in. Within a double for loop, we use indexes i and j to get values within our array and see if they add up to the target sum value. If so, we push it to our answers array. Lastly, we return answers.

Looking at this in terms of runtime, this is probably the worst solution we could create — O(n²).

Binary Search

With the binary search method, we first sort the array. That way, we can take more educated guesses at the target number. First, let’s create a helper method that inputs and array and target value — and outputs true or false if…