Pairwise programming challenge - Free code camp

Question

Challenge:

Given an array arr, find element pairs whose sum equal the second argument arg and return the sum of their indices.

If multiple pairs, that have the same numeric elements but different indices are possible, return the smallest sum of indices. Once an element has been used, it cannot be reused to pair with another.

For example pairwise([7, 9, 11, 13, 15], 20) returns 6.

My code (works, passes all validations) is the below:

function pairwise(list, sum) {
 // noprotect
 var innerCounter,
 outerCounter,
 used = {},
 returnValue = 0;
 for( outerCounter = 0 ; outerCounter < list.length-1 ; outerCounter++){
 if( used[outerCounter] )
 continue;
 for( innerCounter = outerCounter+1 ; innerCounter < list.length ; innerCounter++){
 if( used[innerCounter] )
 continue; 
 if( list[innerCounter] + list[outerCounter] == sum ){
 used[innerCounter] = true;
 returnValue = returnValue + innerCounter + outerCounter;
 break;
 } 
 }
 }
 return returnValue;
}

I had some internal debate on sum as a parameter name, since we also return a sum. But I stuck to returnValue for the return value and sum for the parameter. Any feedback on this is welcome, from style to algorithm.

• 200_success: Are the elements of list necessarily distinct?
• konijn: @200_success Not at all. In fact [0,0,0,1,1],1 is a test case.

Answer 1

My only comments would be stylistic so may be more a matter of opinion. Am open to any counter comments.

Whitespace

All your code is bunched together and is not as easy to read as it could be.

Single Statement if braces

It is often beneficial and consistent to always have braces on if and other blocks even if there is only a single statement. It's easy to introduce undesirable functionality if you come back to the code later and comment/add lines e.g.

if(someValue)
 //doThis();
alwaysDoThis();

Shorthand arithmetic

returnValue = returnValue + innerCounter + outerCounter;

can be shortened to

returnValue += innerCounter + outerCounter;

Answer 2

1. Algorithm

   Your code proposes a nested loop, which may indicate a high time complexity. I believe more efficient implementations exist, possibly at the price of an increased code complexity.

   Rather than search ahead for a complement of the current value, I think it would be more interesting to store the complement of the current value, then move on - each time checking whether the current value matches an already stored complement. The first script below illustrates this approach.

   Also, in such problems, it is always instructive to examine how sorting the initial set can further improve the algorithm. In this occurrence, provided the sorted values retain their initial index, the benefits are interesting: you can iterate from the start and end of the set at the same time, matching values as you go, until iterators cross over. The second script below illustrates this approach.

2. Style

   Even though there is no block-scoping in JavaScript, you should not declare all your variables at once at the top of the function, but rather declare them when they are used. A reviewer will keep his eyes in the same code area, which will facilitate his understanding.

   As pointed out by Tony, you should always use curly braces, even if it is to surround a single statement. This way, reviewers do not have to worry about comments or semi-colons insidiously invalidating the code logic.

   Finally, your internal debate on the naming of the returned value is quite interesting. You should indeed strive to make variables self-explanatory and readable. In your case, since you return the sum of indices, an appropriate variable name would be... sumOfIndices.

3. Illustrations

   1. Storing complements:

      function pairwise(list, sum) {
       var sumOfIndices = 0;
       var complements = {};
       for(var ii = 0; ii < list.length; ii++) {
       var value = list[ii];
       var complement = sum - value;
       if (typeof complements[complement] == "undefined") {
       var stored = complements[value];
       if (typeof stored == "undefined") {
       stored = (complements[value] = []);
       }
       stored.push(ii);
       } else {
       var matches = complements[complement];
       sumOfIndices += matches.pop() + ii;
       if (matches.length == 0) {
       delete complements[complement];
       }
       }
       }
       return sumOfIndices;
      }
      

   2. Sorting values:

      function pairwise(list, sum) {
       var sumOfIndices = 0;
       var entries = list.map((value, index) => { return {value: value, index: index}; });
       entries.sort(function(a, b) {
       if (a.value < b.value) { return -1; }
       if (a.value > b.value) { return +1; }
       return 0;
       });
       var ii = entries.length - 1;
       for(; ii > 0; ii--) {
       if (entries[ii].value <= sum) { break; }
       }
       for(var j = 0; j < ii; j++) {
       var first = entries[j];
       for(; ii > j; ii--) {
       var second = entries[ii];
       if (first.value + second.value > sum) {
       continue;
       }
       if (first.value + second.value == sum) {
       sumOfIndices += first.index + second.index;
       ii--; // Skip last match.
       }
       break;
       }
       }
       return sumOfIndices;
      }