The “Two Sum” algorithm problem is a frequently-asked interview question because it offers multiple solutions and allows candidates to showcase their proficiency in optimising time and space complexity.

Let’s delve into the “Two Sum” problem and explore four different solutions, each with its own time and space complexity considerations.

Problem

Write a function that accepts an array of integers and a target value. The function should return an array containing two numbers from the input array that sum up to the target value. The order of the numbers in the returned array may be reversed. If no such pair exists that adds up to the target, the function should return an empty array. Each number in the input array should only be used once.

Example

Input

Given numbers = [2, -3, 5, 11, -8, 7, 16]
target = 23

Output

[7, 16]

Solution 1 – Brute force

Time complexity: O(n²)
Space complexity: O(1)

Firstly, we’ll examine the brute-force approach. While this method is not particularly efficient, as it requires multiple iterations over the array to find the correct pair, it serves as a starting point. After this, we’ll delve into more optimised solutions in subsequent sections.

Here is the brute force solution.

function twoSum(array, target) {
  for (let i = 0; i < array.length - 1; i++) {
    const numOne = array[i];

    for (let j = i + 1; j < array.length; j++) {
      const numTwo = array[j];

      if (numOne + numTwo === target) {
        return [numOne, numTwo];
      }
    }
  }

  return [];
}

This solution employs a pair of nested loops to traverse the entire array.

In the outer loop, which begins on line 2, the iteration starts at the array's first element and continues up to the second-to-last element. This is because the last element is reserved for comparison in the inner loop. The inner loop starts on line 5 and iterates from the element immediately following the current element in the outer loop all the way to the array's last element.

During each iteration, the outer loop provides a value referred to as numOne, while the inner loop cycles through remaining array values as numTwo.

For example, in the first iteration, numOne is set to 2. The inner loop then iterates through the array elements -3, 5, 11, -8, 7, 16, comparing the sum of numOne and each numTwo against a target number (as specified in line 8). If no match is found, the process proceeds to the next iteration.

In the second iteration, numOne takes the value of -3. The inner loop then cycles through the remaining array elements 5, 11, -8, 7, 16 as numTwo. Since the sum of numOne and any numTwo value does not match the target number, the algorithm advances to the third iteration.

In the third iteration, numOne is set to 5. The inner loop proceeds to iterate over the subsequent array elements, which are 11, -8, 7, 16, acting as numTwo. Since no combination of numOne and numTwo yields the target sum, the algorithm moves on to the next iteration.

(skipping to the final iteration)

Final iteration: numOne becomes 7, marking the end of the outer loop as it reaches the second-to-last element of the array (as indicated on line 2, array.length - 1). The inner loop sets numTwo to 16. Since the sum of 7 and 16 matches the target value of 23, the algorithm returns an array containing both numOne and numTwo (as specified in line 9).

Complexity Analysis(Big O)

Due to the use of nested loops, the algorithm exhibits a time complexity of O(n^2), which is quadratic. Its space complexity is O(1), or constant time, since it doesn't require additional space for its operations.

Solution 2 - Hash table

Time complexity: O(n)
Space complexity: O(n)

By using a hash table, the algorithm becomes significantly more time-efficient, albeit at the cost of using more memory.

A hash table functions like a mini dictionary that contains key-value pairs. In JavaScript, an object can serve as a hash table, enabling rapid lookups to find the desired number.

Walkthrough

Here's how the hash table approach tackles the problem.

We start with an input array [2, -3, 5, 11, -8, 7, 16] and a target sum 23. We're searching for two numbers in the array that, when added together, equal this target sum. If the current number from the array is x, the equation becomes x + y = 23. Our aim is to return [x, y].

Knowing the value of x, we can calculate y as 23 - x. We then check if this y value exists in the hash table. If it does, [x, y] is our answer. Otherwise, we insert x into the hash table and continue scanning the array until y is found.

Let’s see how it works.

In the first iteration, with x = 2, y is calculated as 21. As 21 isn't in the hash table, we store 2 in the hash table.

Current Hash Table:

{
  2: true,
}

In the second iteration, y is 26, (23 - (-3) = 26) and as 26 is not in the hash table, we will store -3 in the hash table and move to the next value.

Current Hash Table:

{
  2: true,
  -3: true,
}

In the third iteration, y is 18 and it is not in the hash table so we will store 5 and move to next value.

Current Hash Table:

{
  2: true,
  -3: true,
  5: true,
}

The process repeats, adding -3, 5, and so on to the hash table until the final array element 16.

So the current hash table so far is as below and as you can see, the hash table is storing the values from the given array.

{
  2: true,
  -3: true,
  5: true,
  11: true,
  -8: true,
  7: true,
}

In the last iteration, y = 7, (23 - 16 = 7). Since 7 is in the hash table, and thus in the original given array, we find that x = 16 and y = 7 satisfy our requirement, and we return them as an array.

Solution with hash table

Here is the solution with the hash table.

function twoSum(array, target) {
  const numsIndices = {};

  for (const num of array) {
    const curDiff = target - num;
  
    if (curDiff in numsIndices) {
      return [num, curDiff];
    } else {
      numsIndices[num] = true;
    }
  }

  return [];
}

We are initialising the hash table, numsIndices (line 2) and check if curDiff (which is y) is in the hash table (line 7). If it is in the hash table, we will return num and curDiff, otherwise we will store the num (which is x) in the hash table.

Complexity Analysis(Big O)

The time complexity is O(n). The main advantage of using a hash table is its constant-time look-up, which allows for a more efficient search without needing to examine every possible array combination.

The space complexity is also O(n) as the hash table requires additional storage space for each array element.

Solution 3 - Binary search

Time complexity: O(nlog(n))
Space complexity: O(1)

Binary search offers a time-efficient solution over the brute force method for the Two Sum problem, while also maintaining constant space complexity.

For a detailed dive into the binary search algorithm, refer to the previously covered article, "Binary Search Algorithm in JavaScript".

Let’s go through the walkthrough and see how we can use the binary search to find the two num sum.

Walkthrough

As we are going to use the binary search algorithm, we first need to sort the array as the binary search only works with the sorted array. We could use a good sorting algorithm like merge sort or quick sort and this is going to run O(nlog(n)). My another article shows you how to sort the array using the bubble sort. For this article though, we are going to use the sort method which you will see in the code solution below.

After the sorting, we are going to have the sorted array like below.

Sorted array = [-8, -3, 2, 5, 7, 11, 16]
Target = 23

Once sorted, we loop through the array. For each iteration, we calculate the needed counterpart by subtracting the current value from the target. We then use binary search to determine if this counterpart exists in the array.

Here's a breakdown.

1st loop (`-8`)

In the 1st loop, we will check the first index value, -8 , against the target value, 23. As we know those two values, what we need to do is to find the other number, 31, from the sorted array using the binary search. If you are not sure why 31 , it’s obtained from 23 - (-8).

As there is no 31 in the array, we will go to the next loop.

2nd loop (`-3`)

In the 2nd loop, we will check if we can find 26 which is coming from 23 - (-3) and as there is no 26 in the array, we will go to the next loop.

3rd loop (`2`)

In the 3rd loop, we will find 21 and as there is no 21 in the array, we will go to the next loop.

4th loop (`5`)

In the 4th loop, we will search for 18 and no 18 in the array, we will go to the next loop.

5th loop (`7`)

In the 5th loop, we identify its counterpart 16 in the array. Thus, 7 and 16 are the two numbers that, when combined, give our target of 23 so we will return 7 and 16.

Solution with binary search

Here is the solution with the binary search.

function twoSum(array, target) {
  const sortedArr = array.sort((a, b) => a - b);

  for (const num of sortedArr) {
    const diff = binarySearch(sortedArr, target - num);
    
    if (diff) return [num, diff];
  }

  return [];
}

First we need to sort the array (line 2) as the binary search only works with the sorted array.

And then we will go through each value of the sorted array (line 4). In each iteration, we will use the binary search with two arguments, the sorted array and the second value we are looking for (line 5). If we found the second value, diff, then we will return the two numbers (line 7). Otherwise, it will end the iteration and return an empty array (line 10).

Complexity Analysis(Big O)

The time complexity is O(nlog(n)). Sorting array (line 2) with a good sorting algorithm like the merge or quick sort is O(nlog(n)). And the for loop (line 4) itself is O(n) and the binary search is O(log(n)) which will result O(n * log(n)). That will give us O(2nlog(n)) but we don’t really care about the constant value 2 for the big picture, it will finally give us O(nlog(n)).

The space complexity is constant, O(1), as we don’t store any value in the increasing size.

Solution 4 - Two-Pointer Technique

Time complexity: O(nlog(n))
Space complexity: O(1)

The Two-Pointer technique employs two pointers on an array: one starting at the beginning and another at the end. By comparing the sum of their corresponding values to the target number, one of the pointers is adjusted until a solution is found.

Let’s get into the walkthrough firstly and see how we can use the two-pointer technique to solve the two sum problem.

Walkthrough

As the two-pointer technique works for the sorted array same as the binary search above, we will sort the given array first.

With the array sorted, two pointers are initialised, referred to as left and right. If the sum of their values matches the target, those values are returned. If the sum surpasses the target, the right pointer is moved one position to the left to decrease the sum. Conversely, if the sum is below the target, the left pointer moves one position to the right.

Let’s go through each iteration.

1st loop

Check if the right pointer (16) + the left pointer (-8) = 8 is equal to the target value, 23. As they are not equal and the sum, 8 , is smaller than the target value, 23, we will move the left pointer to make the sum bigger in the next iteration and get closer to the target value.

2nd loop

Is 16 + (-3) = 13 equal to 23? No and 13 is smaller than the target value so we will move the left pointer.

3rd loop

As 16 + 2= 18 is not equal to the target value and 18 is smaller than the target value, we will move the left pointer.

4th loop

21 is not equal to the target value and 21 is smaller than the target value, we will move the left pointer.

5th loop

As 16 + 7 = 23 is equal to the target value, we will return the left and right pointer.

Solution with two-pointer technique

Here is the solution with the two-pointer technique.

function twoSum(array, target) {
  array.sort((a, b) => a - b);

  let left = 0;
  let right = array.length - 1;
  
  while(left <= right) {
    const sum = array[left] + array[right];

    if (target === sum) {
      return [array[left], array[right]];
    } else if (target < sum) {
      right--;
    } else {
      left++;
    }
  }
  
  return [];
}

First we need to sort the given array as the two-pointer technique works with the sorted array (line 2).

And then we will set the initial left and right pointer (line 4, 5). The left pointer will be set to the first index and the right pointer will be the last index.

We will iterate while the left pointer is equal to or smaller than the right pointer (line 7).

We will sum the value of the left and the right pointer (line 8) and if sum is equal to the target value, we will return the value of the left and right pointer (line 11). If the sum is not equal to the target value and it is bigger than the target, we will move the right pointer (line 13), otherwise we will move the left pointer (line 15). If we can’t find sum equal to the target value from the given array, we will return an empty array (line 19).

Complexity Analysis(Big O)

The time complexity is O(nlog(n)). The good sorting algorithm will take O(nlog(n)) (line 2) and the actual algorithm moving the left and right pointer has a complexity of O(n) as we are going through all the numbers. As a result, it will be O(2nlog(n)) but we don’t worry about the constant value, 2, so the total time complexity will be O(nlog(n)).

The space complexity is O(1) as we don’t use any additional space.