JavaScript Data Structures and Algorithms (Arrays, part 2)

Hello! This is part two of an indeterminate-part series that will introduce you to data structures that you can expect to encounter at a technical interview. Last time I showed some of the basic methods for implementing searching, inserting, deleting, and iterating through an array's elements, as well as each method's time complexity.
I also recommend checking out Mozilla Developer Network for a thorough breakdown of the helper functions available to us with JavaScript. I recommend getting familiar with them as best you can, but don't stress if it seems like a lot to memorize. You can always refer back to it; I know I do.
Anyway, today I thought we'd work on the classic TwoSum algorithm, as a means to practice what we learned in Part 1. I'll be using an example from Apress' JavaScript Data Structures and Algorithms.

"Given an array arr, find and return two indices of the array that add up to weight, or return -1 if there is no combination that adds up to weight. For example, if we have an array [2,5,6,7,10] and the given weight is 9, your code should return [0,3]."

Let's start with a brute-force approach, as in the most obvious approach for solving this problem. Hopefully, the first solution to come to mind was that we can iterate through the array's elements to find our two indices that add up to the given weight. Let's set up this solution and break it down, line by line.

function twoSumArray(arr, weight) {

  for(let i=0; i < arr.length; i++) {
    for(let j=i+1; j < arr.length; j++) {
      if(arr[i] + arr[j] == weight) { 
         return [i, j]
      } 
        }
  }
  return [-1]
}
console.log(twoSumArray([2,5,6,7,10], 9)) //returns [3,4]

As you can see, we are using a loop to iterate through the array to find the first value, i. At the same time, we are iterating through a loop for the second value, j. This is a valid solution, but upon closer inspection, we will find a second nested loop within our first loop. Why is this a problem? Remember that iterating through an array has a time complexity of O(n), where n is the number of elements in an array. In this case, for every element i in the array, we are also iterating for every element j. Now every item in the array gets iterated through twice, 0(n * n). This nested loop makes our function have quadratic time complexity, or O(n^2). The number of steps needed to run this algorithm will increase exponentially for every element, so you can imagine what that can mean in a larger array.

At this point you should step back and think. Can we solve this without iterating twice for every value? Is there a way to iterate through the array only once? How can we lower the time complexity of this function? I can tell you right now that there is. When looking for the two sum values, we are already locking ourselves in to having to iterate twice through the array. In situations like this, I recommend trying to break down the problem backwards. There be less iterating involved if we got the difference between the weight and an index, and check if that value exists in the array. I've included such an approach in the code below:

const twoSumAlt = (arr, weight) => {
  const previousValues = {};
  for (let i = 0; i < arr.length; i++) {
    const complement = weight - arr[i];
      if (previousValues[complement]) {
      return [arr.indexOf(complement), i];
    }
    previousValues[arr[i]] = true;
  }
};
twoSumAlt([2,5,6,7,10],9)) //returns [3,4]

As you can see, we only iterated through the array once without nesting further. As we iterated through each value we stored the difference between the given weight and the current index in a variable previousValues. Then if at any point we found the difference in our array, we would return that value's index and the index i. This function runs in constant time complexity, 0(n), which means the number of steps taken to run this function is equal to the number of values in our input. Taking a step back from your code and communicating your thought process can help you discover other perspectives when writing code, and your ability to communicate your way to an optimized solution will impress your interviewer.

If you're not doing so already, I highly recommend you check out the coding challenges avaliable at LeetCode, including the TwoSum algorithm we just solved here. Next time I will discuss Linked Lists and how to write search, insert, delete, and iteration algorithms for the multiple types of linked lists. Practice, learn, grow, and I'll see you next time!