Free Code Camp - Pairwise

Question

I'm working through the Free Code Camp syllabus and I'm on to Intermediate JavaScript Algorithms. This Pairwise problem was the last challenge in that section. The section came just after "Object Oriented JavaScript." So I figured they were looking for an OO solution, but the instructions included a link to MDN's array.reduce(). My solution doesn't use array.reduce() and I'd really appreciate some feedback on what I could have done better to make my code more compact and efficient. It feels a little clunky but passes all the tests.

The instructions

Return the sum of all indices of elements of 'arr' that can be paired with one other element to form a sum that equals the value in the second argument 'arg'. If multiple sums are possible, return the smallest sum. Once an element has been used, it cannot be reused to pair with another.

For example, pairwise([1, 4, 2, 3, 0, 5], 7) should return 11 because 4, 2, 3 and 5 can be paired with each other to equal 7.

pairwise([1, 3, 2, 4], 4) would only equal 1, because only the first two elements can be paired to equal 4, and the first element has an index of 0!

Remember to use RSAP if you get stuck. Try to pair program. Write your own code.

Here are some helpful links:

Array.reduce()

My Solution

function pairwise(arr, arg) {
    this.objects = [];
    var total = 0;

    function Element(value, index) {
        this.value = value;
        this.index = index;
        this.used = 0;
    }

    for (var i = 0; i < arr.length; i++) {
        this.objects.push(new Element(arr[i], i));
    }

    for (var j = 0; j < objects.length; j++) {
        if (objects[j].used === 0) {
            for (var k = 0; k < objects.length; k++) {
                if (objects[k].used === 0 && objects[k].index != objects[j].index) {
                    if (arg - objects[j].value == objects[k].value) {
                        total = total + objects[j].index + objects[k].index;
                        objects[j].used = 1;
                        objects[k].used = 1;
                        break;
                    }
                }
            }
        }
    }

    return total;
}

pairwise([1,1,1], 2);

Answer 1

I looked through your code and it is a valid solution, but you could reduce your code base by better leveraging the functions that JavaScript already provides, such as Array.prototype.indexOf().

For example, instead of building a new class-like-function (Element) to track the appearance of a certain index, I simply made a deep copy of the the initial array and parsed it with indexOf().

Moreover, in your code, when you first declare this.objects = [], this actually refers to the global scope (window object). As you can see, you are calling pairwise without building a new instance (new keyword). In this case, thus the this keyword is bound to the global window object.

Please find below my take on it:

function pairwise(arr, arg) {

  var result = 0,
      newArr = [],
      //Used to hold the indices that we have already used to form our sum
      indices = [];

  //Loop through arr and create a deep copy of it in newArr
  for(var k = 0; k < arr.length; k++) {
    newArr.push(arr[k]);
  }

  //Loop through arr
  for(var i = 0; i < arr.length; i++) {

    //Loop through newArr
    for(var j = 0; j < newArr.length; j++) {
      //Since we want to add different elements of the array, we want to avoid adding the same element
      if(i !== j) {
        //If the sum of two elements is equal to arg AND the indices that we have in i and j are not part of the indices array
        //Indices array is used to hold the already used indices, thus ensuring the accurate parsing of the parameters
        if(arr[i] + newArr[j] === arg && indices.indexOf(i) === -1 && indices.indexOf(j) === -1) {
          //Sum the indices up
          result += i + j;
          //Push the indices in the indices array in order to not use them in further iterations
          indices.push(i, j);
        }
      }
    }
  }

  return result;
}

pairwise([1,4,2,3,0,5], 7);

Answer 2

Vlad Z answer is correct but freecodecamp has weird wording on this problem. I used a similar answer but was failing on this test:

expect(pairwise([0, 0, 0, 0, 1, 1], 1)).to.equal(10);

My problem and the problem with Vlad Zs solution is that 0,1 -> indexes (0 and 4) and 0,1 indexes(1 and 5) are both acceptable and should return 10.

I would use Vlad's solution but sub in this function instead of indexOf === -1 to check if a pair exists already:

function checkPairExists(value,position,pairsArray){
for(var i = 0; i < pairsArray.length; i++){
   if (pairsArray[i].value === value && pairsArray[i].position === position){
     return true;
   }
}
 return false;
}

Answer 3

This function implementation uses the "reduce" method to get the sum of the indexes and it fullfills all Free Code Camp tests.

function pairwise(arr, arg) {
  return arr.reduce((sum, value1, index1) => {
    arr.slice(index1 + 1).forEach((value2, index2) => {
      if (arr[index1] + arr[index1 + 1 + index2] === arg) {
        arr[index1] = arr[index1 + 1 + index2] = NaN;
        sum += index1 + index1 + 1 + index2;
      }
    });
    return sum;
  }, 0);
}

Answer 4

I came to the same conclusion as Piotr, but with a slight improvement - dropping one more un-necessary check. See comments in code below:

function pairwise(arr, arg) {
  var sum = 0;

  for (var i=0; i < arr.length - 1; i++) {
    for (var j=i+1; j < arr.length; j++) {
        //No need to check for less than arg, used elements are naturally eliminated
        if (arr[i] + arr[j] === arg) {
            sum += i + j;
            arr[i] = arr[j] = arg + 1; //Set the used elements to higher than arg e.g. arg + 1
        }
    }
  }

  return sum;
}

pairwise([1,4,2,3,0,5], 7);

Answer 5

The requirements are broken down into:

• Return the sum of all indices of elements of 'arr' that can be paired with one other element to form a sum that equals the value in the second argument 'arg'.
• If multiple sums are possible, return the smallest sum. Once an element has been used
• Once an element has been used, it cannot be reused to pair with another.

The first bullet point is easy enough to understand. We find pairs that sum up to the total, and sum up the indices.

However, your example contradicts the second bullet point. If multiple sums are found, it should return the smallest. 4 and 3 are 1 and 3 which results to 4. 2 and 5 are 2 and 5 which results to 7. The result should be 4 in the first example.

So here's my take on it

function pairwise(arr, total) {
// For each item in the array
var sums = arr.reduce(function (indexSum, firstNumber, firstIndex) {
    // Collect the pair's index which causes the numbers to sum to total
    var secondIndices = arr.slice(firstIndex + 1).reduce(function (secondIndices, secondNumber, i) {
        if (firstNumber + secondNumber === total) secondIndices.push(firstIndex + i + 1);
        return secondIndices;
    }, []);
    // Add to our collection the sum this iteration's index and
    // the pair indices
    return indexSum.concat(secondIndices.map(function (secondIndex) {
        return secondIndex + firstIndex
    }));
}, []);
// In all the items, find the smallest sum
return Math.min.apply(null, sums);
}

console.log(pairwise([1, 4, 2, 3, 0, 5], 7));
console.log(pairwise([1, 3, 2, 4], 4));

Regarding bullet point 3, I would care less if a number was reused, like in the case of 6 in [4, 4, 2] or say [4, 2, 9, 9, 4] because any number that's going to pair with it after the first established pair will have a higher index sum anyways.

Answer 6

The solution below is very compact. It avoids unnecessary checks and loops only through the relevant elements. You can check the working codepen here: http://codepen.io/PiotrBerebecki/pen/RRGaBZ.

function pairwise(arr, arg) {
  var sum = 0;
  for (var i=0; i<arr.length-1; i++) {
    for (var j=i+1; j<arr.length; j++) {
      if (arr[i] <= arg && arr[j] <= arg && arr[i] + arr[j] == arg) {
        sum += i+j; 
        arr[i] = arr[j] = NaN;
      }   
    }
  }
  return sum;
}

console.log(  pairwise([1, 1, 0, 2], 2)  ) // should return 6

Under the hood:

1. Start looping from the element with index (i) = 0.
2. Add a second loop only for the elements which are later in the array. Their index j is always higher than i as we are adding 1 to i.
3. If both elements (numbers) are less than or equal to to the arg, check if their sum equals to the arg. This avoids checking the sum if either of the numbers are greater than the arg.
4. If the pair has been found then change their values to NaN to avoid further checks and duplication.

Answer 7

Maybe not super efficient, but a little towards FP style:

pairwise = (ary, n) => ary.
  filter(m => ary.some(x => x !== m && m + x === n)).
  map(e => ary.indexOf(e)).
  reduce((a, b) => a + b)

(Not sure why node wouldn’t accept dots in the beginning of line, I would’ve liked them to be there).

Answer 8

An \$O(n)\$ complexity and storage solution

A post dredged from the deep past and has 7 answers. All of which are rather poor in terms of either complexity and/or storage.

There is a solution that is \$O(n)\$ complexity and \$O(n)\$ storage.

Note Best case storage \$O(1)\$ eg (pairwise[0, 0, 0, ..., 0], 0). Worst case \$O(n)\$ eg (pairwise[0, 0, 0, ..., 0], 1)

Using a Map we can eliminate the costly overhead of iterating to find the second matching item. The map also stores an array indexes of the first item allowing for easy calculation of the smallest result. This removes the need to search for the lowest value.

function pairWise(arr, pairSum) {
    const required = new Map();
    var sum = 0, i = 0;
    for (const val of arr) {
        if (required.has(val)) {
            const pair = required.get(val);
            sum += i + pair.ind[pair.use ++];
            if (pair.use === pair.ind.length) { required.delete(val) }
        } else {
            const req = pairSum - val;
            if (required.has(req)) { required.get(req).ind.push(i) }
            else { required.set(req, {ind: [i], use: 0}) }
        }
        i ++;
    }
    return sum;
}

To be fair at the time this question was posted knowledge of Map was limited as was its implementation. However JS Object also provides a way to create a map so the solution has always been easily implemented in JS

// pre ES6 version
function pairWise(arr, pairSum) {
    var required= {}, sum = 0, i = 0, val, pair;
    while (i < arr.length) {
        val = arr[i];
        if (required[val]) {
            pair = required[val];
            sum += i + pair.ind[pair.use ++];
            if (pair.use === pair.ind.length) { delete required[val] }
        } else {
            val = pairSum - val;
            if (required[val]) { required[val].ind.push(i) }
            else { required[val] = {ind: [i], use : 0} }
        }
        i ++;
    }
    return sum;
}