One Pager Cheat Sheet

• Given an array of integers and a target number, find the indices of the two numbers which add up to the target, without using the same element twice and providing a solution with an expected time complexity of O(n) and an expected space complexity of O(n).
• We can solve this problem by iterating through each element of the array and comparing it against every other element, using a nested for-loop.
• We can reduce the time complexity from O(n^2) to O(n) by using a hash map to keep track of the difference between the goal and values at each index of our input array.
• The time complexity of this O(n) solution is O(n) and has an equal space complexity, as we can iterate through the elements once and store them in a hash map.
• We can use Two Pointers to efficiently traverse through a sorted array and find a pair of numbers that add up to a given sum.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function twoSum(arr, goal) {

  const results = [];

  const hash = {};

​

  for (let idx in arr) {

    const difference = goal - arr[idx];

    if (hash.hasOwnProperty(arr[idx])) {

      results[0] = parseInt(hash[arr[idx]]);

      results[1] = parseInt(idx);

    } else {

      hash[difference] = idx;

    }

  }

​

  return results;

}

​

try {

  assert.deepEqual(twoSum([1, 9, 13, 20, 47], 10), [0, 1]);

​

  console.log(

    'PASSED: ' + 'assert.deepEqual(twoSum([1, 9, 13, 20, 47], 10), [0, 1]);'

  );

} catch (err) {

  console.log(err);

}

​

try {

  assert.deepEqual(twoSum([3, 2, 4, 1, 9], 12), [0, 4]);

​

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.