Solving a Common Interview Question: the Two Sum Algorithm in JavaScript

Imagine you’re at a lively party, and everyone is carrying a specific number on their back. The host announces a game – find two people whose numbers add up to the magic number, and you win a prize!

This scenario perfectly captures the essence of the Two Sum Problem, a beloved classic in the world of algorithm challenges.

In this article, we’ll be taking a look at two different solutions to the problem. So let’s jump in!

Introduction: Two Sum

Objective: Given an array of integers, return the indices of the two numbers such that they add up to a specific target. For example, if the input is 10, and we have an array [5, 1, 5, 3], the return value should be [0, 2], because index 0 is 5, and index 2 is also 5, which adds up to 10, the target value.

This problem may sound simple, but it opens the door to a multitude of approaches, from brute force to more elegant optimizations. The first solution below is a bit iffy, but fret not, we’ll speed it up a bit in the second!

Solution 1: The Brute Force Dance

The first approach is like a classic dance move – simple but effective. We check every possible pair in the array to see if their sum matches the target.

Let’s look at some pseudocode before diving into the solution.

// Iterate through each element
// For each element, iterate through the elements that come after it, e.g. nums[j] where j > i.
// If nums[i] + nums[j] === target
//// return the indices.

Try to solve it before proceeding!

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

Now, I have to ask… Does this algorithm look efficient to you?

What would happen if the input contained an array with one million or more elements? Well, in that case, the code may take forever to run.

The time complexity of the solution above is O(n^2). Can we do better? Of course!

Let’s upgrade our code to be more efficient with the use of a hash map.

Solution 2: Speed it up with Hash Map

The solution I’m about to show you uses a hash map to store the indices of the elements we’ve seen so far. A hash map (or hash table) is a data structure that stores key-value pairs, allowing for fast retrieval of values based on their keys through a process called hashing.

This way, we can find the complement of the current element in constant time. (The rationale behind naming the variable complement is that for any given element nums[i], we are looking for another element in the array such that their sum is equal to the target. This other element is the complement of the current element with respect to the target sum.)

Again, let’s start with some pseudocode:

// Create an empty hash map 
// Iterate through each element nums[i]
// Calculate: complement = target - nums[i].
// if complement is already in the hash map:
//// return the indices [numToIndex[complement], i] 
// add nums[i] to the hash map with its index i 

Try to solve it before looking down below!

.

.

.

function twoSumHashMap(nums, target) {
  const numToIndex = {};

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    
    if (numToIndex[complement] !== undefined) {
      return [numToIndex[complement], i];
    }

    numToIndex[nums[i]] = i;
  }
  return null;
}
console.log(twoSumHashMap([2, 7, 11, 15], 9)); // [0, 1]

This algoritm is a lot quicker than the previous one, although it indeed extra space for the hash map (O(n) space complexity).

Note: The phrase above, we can find the complement of the current element in constant time refers to the time it takes to check if the complement exists in the hash map, which is indeed O(1) for each individual lookup.

However, since we need to perform this check for each element in the array, the overall time complexity for the entire algorithm is O(n).

Conclusion

There we have it, a very fun algorithm challenge with two different solutions. We hope this article better prepares you for your next interview.

Have you ever been asked to solve this algorithm in an interview setting? If so, let us know in the comments below! Likewise, if you are an interviewer and you have asked this question, let us know how the candidate performed!