I want a help in optimising a solution of a problem, I already sort out the problem, but my code is not good enough for handling large array - codeWars : Sum of Pairs - problem

Here is my code -

var sum_pairs=function(e, sum){

var result=null;
var arrLen=e.length;
for(let i=0;i<arrLen-1;i++){
  let nextIndex=e.slice(i+1,arrLen).indexOf(sum-e[i]);
  if(nextIndex>=0){ 
    result=[e[i],e[nextIndex+1+i]];
    arrLen=nextIndex+1+i; 
  }
}
return result;
}

Well, I know this is not a good solution. Anyway, this passes all the test cases but failed when it encounter large array - Result On codewars

I want to know how to optimise this code, and also Learn any technique to writing a good code.

I want a help in optimising a solution of a problem, I already sort out the problem, but my code is not good enough for handling large array - codeWars : Sum of Pairs - problem

Here is my code -

var sum_pairs=function(e, sum){

var result=null;
var arrLen=e.length;
for(let i=0;i<arrLen-1;i++){
  let nextIndex=e.slice(i+1,arrLen).indexOf(sum-e[i]);
  if(nextIndex>=0){ 
    result=[e[i],e[nextIndex+1+i]];
    arrLen=nextIndex+1+i; 
  }
}
return result;
}

Well, I know this is not a good solution. Anyway, this passes all the test cases but failed when it encounter large array - Result On codewars

I want to know how to optimise this code, and also Learn any technique to writing a good code.

• javascript
• arrays
• algorithm
• memoization

• Here is link - codewars./kata/sum-of-pairs/train/javascript – Aditya Mishra Commented Feb 16, 2017 at 10:01
• (Here is link - replace the image reference in your question with that (train/<language> part or not).) The problem is ill defined: What is the definition of order of appearance, when is a pair earlier? If it was lowest index first, you just have to know if there is a value at a different index that sums to the given sum. If it is lowest sum of indices, with lowest index to break ties, you need to get smarter… (Note that you are wele to answer your own question.) – greybeard Commented Feb 16, 2017 at 10:55
• I want to know how to optimise this code - don't - the algorithm is not up to handling sizeable arrays. I want to [… learn] any technique [for writing] good code You started with The most simple thing that might work: good. You consider each index as a possible first index - looks inevitable. Disregarding, for the moment, the plexity of ECMAScript slice: How much effort is each membership query using indexOf(sum-e[i])? Total effort? What is the required result, and what does your sum_pairs do once a matching pair has been found? (Imagine an array of 10,000,000 zeros, sum zero) – greybeard Commented Feb 16, 2017 at 12:53
• @greybeard you mean to say let nextIndex=e.slice(i+1,arrLen).indexOf(sum-e[i]); this line taking more time, – Aditya Mishra Commented Feb 16, 2017 at 13:07
• I fully expect array.indexOf(value) to take time linear in the number of elements/_length_ of array (in an unsuccessful search). more time pared to what? That is definitely where a lot of time is going, in addition to not stopping the moment you know the result. – greybeard Commented Feb 16, 2017 at 14:22

2 Answers 2

One solution is to use Set data structure to memorize the numbers all ready iterated over. Then we can check for each element if there has been a number which sums to s. The set has an average constant time plexity for insert and search making the algorithm linear in time (and space).

var sum_pairs=function(ints, s){
  if (ints.length < 2) return undefined; //not enough numbers for pair.
  let intSet = new Set()
  intSet.add(ints[0]);
  for (let i=1; i < ints.length; ++i){
    let needed = s-ints[i];
    if (intSet.has(needed)){//check if we have already seen the number needed to plete the pair.
      return [needed,ints[i]];
    }
    intSet.add(ints[i]);//if not insert the number in set and continue.
  }
  return undefined;//No answer found
}

function sumPairs (ints, s) {
 if (ints.length<2) return undefined
  let inSet = new Set()
  for (let i= 0;i<ints.length;i++){
    let need = s-ints[i]
    if( inSet.has(need)){
      return [need,ints[i]]
    }
    inSet.add(ints[i])
  }
  return undefined
}