solving the 2-sum algorithm in javascript

Question

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.

There's [a very concise solution](http://stackoverflow.com/a/4720397/975097) to this problem that would be relatively easy to translate into JavaScript. — Anderson Green, Nov 18 '16 at 04:06
On the second pass of your loop 7-4 is 3. Are you operating on a separate math plane than the rest of the planet? `hashTable[3]` would still be 3. — StackSlave, Nov 18 '16 at 04:10
@PHPglue sorry I'm really not sure what you are getting at. its an unsorted list and the value 3 happens to be at index 3. — Solomon Bothwell, Nov 18 '16 at 04:23
Dynamical programming bottom to up approach should be the best — Redu, Nov 18 '16 at 09:35

Yeldar Kurmangaliyev · Accepted Answer · 2016-11-18T04:22:51.223

1

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]); 
})

edited Nov 18 '16 at 04:22

answered Nov 18 '16 at 04:07

Yeldar Kurmangaliyev

32,279
11
59
94

hmm. yes i see that makes sense. your change fixed it when i = 1 but when i = 3 the output is [1,3] (because the key 4 in hashTable has value 1). – Solomon Bothwell Nov 18 '16 at 04:19
@SolomonBothwell Oh, yes, you need to wrap the first summand with `arr[]` too, since you need its value too. See my updated answer. – Yeldar Kurmangaliyev Nov 18 '16 at 04:23
Oh I see! Thanks so much. Your shortened answer looks really cool too. Im studying it right now. – Solomon Bothwell Nov 18 '16 at 04:27
1

I noticed a bug in both versions. Change the target value to 4 and it will sum the same element (2 in this case). Adding [arg - x] != x to the if statement solves this. – Solomon Bothwell Nov 18 '16 at 04:47
Actually scratch my last comment. That fix only works if there are no duplicate values in the array. Try running it with arr = [1, 1, 1] and arg = 2 – Solomon Bothwell Nov 18 '16 at 05:43

score 1 · Answer 2 · answered May 28 '19 at 06:40

1

function solution(arr, n){
var map = {};
for (var i = 0; i < arr.length; i++) {
    if (map[arr[i]] !== undefined) {
        console.log(arr[i], n - arr[i]);
    }
    map[n - arr[i]] = i;
  }
 }

answered May 28 '19 at 06:40

daniel gi

367
1
6
18

score 0 · Answer 3 · answered Nov 18 '16 at 04:27

Try this out:

function sumPairs(inputArray, expectedSum){
  var a = inputArray.slice(), b = inputArray.slice(), l = a.length, p = [];
  for(var i=0,av; i<l; i++){
    av = a[i];
    for(var n=1,bv; n<l; n++){
      bv = b[n];
      if(av + bv === expectedSum){
        p.push([av, bv]);
      }
    }
  }
  return p;
}
console.log(sumPairs([1,4,2,3,0,5], 7));

score 0 · Answer 4 · answered Dec 10 '19 at 19:04

Below Function working fine for multiple cases.

   const twoSum = (numArr, target) => { 
        let numObject = {};
        numArr.forEach((value, index) => numObject[value] = index);
        for (let i = 0; i < numArr.length; i++) {
            let diff = target - numArr[i];
            if (numObject.hasOwnProperty(diff) && numObject[diff] !== i) {
                return [i, numObject[diff]];
            }
        }
    }

score 0 · Answer 5 · answered Sep 12 '21 at 03:55

0

const arr = [1, 2, 3, 4,5,6];
let target = 9;
let indexs = [];
function sumNew(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if ( arr[i] + arr[j]==target) {
               indexs.push(i,j);
               return indexs;
            }

        }
    }
}
let result = sumNew(arr,target);
console.log(result);

answered Sep 12 '21 at 03:55

Gaurav

11
2

1

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers [in the help center](/help/how-to-ask). – Community Sep 12 '21 at 04:15

solving the 2-sum algorithm in javascript

5 Answers5