Two Approaches to Solving The TwoSum Problem – Easy Javascript Implementation

If you’ve been practicing some data structures and algorithms, then you have probably come across the TwoSum problem. It’s a popular and easy question to help you get started.

The problem can be asked in multiple ways. We’ll go for the generic question as seen on leetcode.

Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Example:

Given nums = [2, 7, 11, 15], target = 9

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

The Brute Force (Wrong) Approach

After reading the question, it makes sense to immediately assume iterating through the array at a higher and lower level. This could be achieved with a for loop that keeps track of the current element in the array, and a faster sub loop that checks if any of the other elements in the array add up to our target.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {
  for (i = 0; i < nums.length; i++) {
    for (j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        console.log([i, j]);

        return [i, j];
      }
    }
  }
}

twoSum([2, 7, 11, 15], 9);

The problem with this approach is that it’s brute forced and contains two unnecessary loops which increases the time complexity. The time complexity here is 0(n^2). Let’s check out the two approaches below.

First Approach: Complements Solution

We can do better than the above by using a complement approach. In math, a complement is the amount you must add to something to make it whole. Using this concept, we define a `complementArray` to keep track of the difference of the target and values in the array as we loop through.

We define a for loop and check, if the difference of target and value exist in the complement array, if it does, then we’ve found our match, else, we push/add the difference to the complements array.

/** 
* @param {number[]} nums 
* @param {number} target 
* @return {number[]} 
*/
function complementSolution(nums, target) {
    complementArray = [];

    for (i = 0; i < nums.length; i++) {
        differenceOfTargetAndValueAtIndex = target - nums[i];
        if (complementArray.includes(nums[i])) {
            return [
                complementArray.indexOf(nums[i]),
                i
            ];
        }

        complementArray[i] = differenceOfTargetAndValueAtIndex;
    }
}

complementSolution([2, 7, 11, 15], 9);

The time complexity for the above will be 0(n). Space complexity will also be 0(n) since we have allocated space to storing the complements.

Second Approach: Pointer Solution

This is probably my prefered approach because it is simpler and much faster. We set two pointers, a fast pointer and a slow pointer. The slow pointer starts at index 0 and the fast pointer at slow pointer index + 1. In a loop, while the slow pointer is less than the size of the array, we move the fast pointer, iterating from position 1 till the end of the array.

If we encounter values at the slow and fast pointers that add up to the target, we return the indices, else we increment the slow pointer and reset the fast pointer to slow pointer position + 1.

/** 
* @param {number[]} nums 
* @param {number} target 
* @return {number[]} 
*/
function pointerSolution(nums, target) {
    slowPointer = 0;
    fastPointer = 1;

    while (slowPointer <= nums.length - 1) {
        if (nums[slowPointer] + nums[fastPointer] === target) {
            return [
                nums.indexOf(nums[slowPointer]),
                nums.indexOf(nums[fastPointer])
            ];
        }

        if (fastPointer < nums.length - 1) {
            fastPointer++;
        } else {
            slowPointer++;
            fastPointer = slowPointer + 1;
        }
    }
}

pointerSolution([2, 7, 11, 15], 9);

The time complexity for the above will be 0(n). Space complexity will  be 0(1) since we have not allocated any additional space to keeping track of the values in the array.

I hope this was helpful and if you have an approach to share? or found an error? Please let me know in the comment section below.

Thanks for reading.