Solomon Bothwell Solomon Bothwell - 21 days ago 10
Javascript Question

solving the 2-sum algorithm in javascript

I'm trying to write a simple solution to the 2-Sum problem in Javascript. The problem goes: given an array of n integers and a target sum, determine what combinations of two integers will sum to the target value.

I found a few different language agnostic examples using hash tables and tried to come up with a solution in javascript:

// Integer set:
arr = [1,4,2,3,0,5];
// Target sum:
arg = 7;

// Generate hash table
hashTable = {};
arr.forEach(function(value, index){
hashTable[value] = index;
});

// hashTable = {
// 0: 4,
// 1: 0,
// 2: 2,
// 3: 3,
// 4: 1,
// 5: 5,
// }


for (var i = 0; i < arr.length; i++) {
if (hashTable[arg - arr[i]]) {
console.log([hashTable[arg - arr[i]], i])
}
}


The solution should be 4,3 and 5,2 but i am getting 3,1 5,2 1,3 and 2,5. I can walk through the for loop with pen and paper and see that I am doing something wrong but I'm pretty sure I am following the langauge agnostic examples I found (for example here and here). Any help would be appreciated.

Answer

Here, you output indices of summands, while you need its values:

 console.log([hashTable[arg - arr[i]], i])

That's why you get these values:

  • 3, 1; which means item at index 3 + item at index 1 = 7
  • 5, 2; which means item at index 5 + item at index 2 = 7 etc.

Try changing i in output to arr[i], and hashTable[arg - arr[i]] to arr[hashTable[arg - arr[i]]], it should work:

// Integer set:
var arr = [1,4,2,3,0,5];
// Target sum:
var arg = 7;

// Generate hash table
var hashTable = {};
arr.forEach(function(value, index){ 
  hashTable[value] = index;
});


for (var i = 0; i < arr.length; i++) {
  if (hashTable[arg - arr[i]]) {
      console.log([arr[hashTable[arg - arr[i]]], arr[i]]);
  }
}

Note that you get symmetric results too because 4 + 3 = 7 and 3 + 4 = 7 as well.
The solution can be optimized by checking while inserting:

var arr = [1, 4, 2, 3, 0, 5];
var arg = 7;

var hashtable = {};
arr.forEach(function(x) { 
  hashtable[x] = true;
  if (hashtable[arg - x]) 
    console.log([arg - x, x]); 
})