Two sum algorithm in Javascript

Two sum Algorithm will take in an array and a given number and will check of all pairs of number in the array that will adds up and equals the given number, So keep in mind that result will be an array of arrays, Any number can be used in multiple arrays.

There are many ways to solve this in O(n^2) and O(n), with that in mind O(n) is more performant we will use hashtable and make use of numbers counter part.

##Example

array: [1,6,4,5,3,3]
sum: 7
output: [ [ 6, 1 ], [ 3, 4 ], [ 3, 4 ] ]

Input : array, number
Output : Array of arrays.

Implementation with O(n^2) #

function twoSum(array, num) {
  var result = [];
  for (var i = 0; i < array.length; i++) {
    for (var j = i + 1; j < array.length; j++) {
      if (array[i] + array[j] === num) {
        result.push([array[i], array[j]]);
      }
    }
  }

  return result;
}

Implementation with O(n) #

function twoSum(array, num) {
  var result = [];
  var hashtable = [];
  for (var i = 0; i < array.length; i++) {
    var currentValue = array[i];
    var counterPart = num - currentValue;
    if (hashtable.indexOf(counterPart) != -1) {
      result.push([currentValue, counterPart]);
    }
    hashtable.push(currentValue);
  }
  return result;
}

Main Point: Time Complixity.

The code is availalbe here : https://repl.it/@ahmd1/TwoSum

Credits #

Photo by The Creative Exchange

← Home