2
\$\begingroup\$

The following function sum_pairs takes two arguments one array and another number, It should return the first two values (parse from the left please) in order of appearance that adds up to form the sum. Negative numbers and duplicate numbers can and appear.

For example

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#              ^-----------^   5 + 5 = 10, indices: 1, 5
#                    ^--^      3 + 7 = 10, indices: 3, 4 *
#  * entire pair is earlier, and therefore is the correct answer
== [3, 7]

My following code works but takes time. I know it can be optimized but can't think how can I replace any of the loops.

var sum_pairs=function(ints, s){
  var result = [];
  var finalResult = undefined

  for(let i = 0; i < ints.length; i++){
    var anotherArray = ints.slice()
    anotherArray[i] = 0
    for(let j = 0; j < anotherArray.length; j++){
      var sum = ints[i] + anotherArray[j]
      if(sum === s){
        var tempResult = []
        tempResult.push(i)
        tempResult.push(j)
        result.push(tempResult)
      } 
    }
  }

  var resultArray = []
  result.map((array, index) => {
    array.map((number, idx) => {
      array[idx] === array[idx+1] ? result.splice(index, 1) : false      
      array.every((num, i) => i === array.length - 1 || num < array[i + 1]) ? resultArray = array : false
    })
  })

  s === 0 ? 
  finalResult = [0, 0] : resultArray.length === 0 ? 
  finalResult = undefined : finalResult = [ints[resultArray[0]], ints[resultArray[1]]]


  return finalResult
} 

Any suggestion to optimize further?

\$\endgroup\$
  • \$\begingroup\$ This is a duplicate of Codewars: Sum of Pairs and the code in my answer runs 10 times faster than yours which is noticeable of course only on large number of repetitions or on large arrays. \$\endgroup\$ – wOxxOm Sep 27 '17 at 19:46
4
\$\begingroup\$

Bug

The implementation doesn't work well with duplicate numbers:

console.log(sum_pairs([10, 5, 5, 3, 7, 4], 10));
[ 3, 7 ]

That output should be [ 5, 5 ].

Also, for sum_pairs([10, 5, 2, 3, 7, 5], 8) I would have expected [ 5, 3 ] instead of [ 3, 5 ] as the output. You didn't mention that results should be sorted.

The slowness

I see several reasons for the slowness:

  • The implementation is quadratic, using a nested loop
  • The implementation uses several expensive operations, such as slice and splice of arrays

Also, the implementation is extremely complicated and hard to follow, so there might be other causes too.

A simpler solution is possible if you track the elements seen so far in an object, and check if target - current was seen or not.

var sum_pairs = function(ints, s) {
  var seen = {};

  for (let i = 0; i < ints.length; i++) {
    let num = ints[i];
    if (seen[s - num]) {
      return [s - num, num];
    }
    seen[num] = true;
  }
} 
\$\endgroup\$
  • \$\begingroup\$ After reading your suggested solution, I feel like I made a simple thing complicated! And your solution also works perfectly. I apologize, I don't have enough reputation to upvote your answer. \$\endgroup\$ – Hima Chhag Sep 28 '17 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.