DailyCodingProblem, find pair in array that matches a given value

Question

I'm fairly new to coding and enlisted for the daily coding problem mailing list and got this question:

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

My solution (after some stackoverflow digging) looks like this;

function problemOne_Solve()
{
    const k = 17;
    const values = [11, 15, 3, 8, 2];
    for (i=0; i < values.length; i++) {
        if ( values.find( (sum) => { return k-values[i] === sum} ) ) return true;
    }
    return false;
}

I'm wondering why it works. To me it looks like the part with the fat-arrow function closes the brackets inside the if statements conditional logic. And there is no such brackets after the if statement, which I thought was required.

I was also wondering how i would go about outputting the pair or pairs that sums up to "k," to build further on the solution. I would like to be able to display the pairs on the page for example.

Answer 1

.find takes a callback, which is invoked for every item in the array (or, up until a match is found). The first argument to the callback is the item being iterated over. If a match is found (if the return value from the callback was truthy for any element), the .find returns the item that resulted in a truthy return value.

So, on the first i = 0 iteration, and values[i] is 11, (sum) => { return k-values[i] === sum} will first check whether 17 - 11 === 11, and then whether 17 - 11 === 15, and then whether 17 - 11 = 3, etc.

This condition will generally be fulfilled if two numbers in the array add up to the k, but the algorithm is buggy. For example, an array composed of [1] will check the 1 against itself on the first iteration, adding up to 2:

function problemOne_Solve() {
    const k = 2;
    const values = [1];
    for (i=0; i < values.length; i++) {
        if ( values.find( (sum) => { return k-values[i] === sum} ) ) return true;
    }
    return false;
}

console.log(problemOne_Solve());

That is wrong. Another problem is that .find returns the found value. But, if the array is an array of numbers, the found value may be 0, and 0 is falsey. So the below example should return true because two elements sum up to 0 (0 and 0), but it returns false:

function problemOne_Solve() {
    const k = 0;
    const values = [0, 0];
    for (i=0; i < values.length; i++) {
        if ( values.find( (sum) => { return k-values[i] === sum} ) ) return true;
    }
    return false;
}

console.log(problemOne_Solve());

To get it right and decrease the computational complexity from O(n ^ 2) to O(n), iterate over the array once. Create an object whose keys are the numbers being iterated over, and on each iteration, check to see if a key of target - currNum exists on the object (where target is the target sum, and currNum is the current number from the array):

function problemOne_Solve() {
  const target = 17;
  const values = [11, 15, 3, 8, 2];
  const obj = {};
  for (const currNum of values) {
    if (obj.hasOwnProperty(target - currNum)) {
      return true;
    }
    obj[currNum] = true;
  }
  return false;
}
console.log(problemOne_Solve());

I was also wondering how i would go about outputting the pair or pairs that sums up to "k," to build further on the solution. I would like to be able to display the pairs on the page for example.

Instead of returning immediately when a match is found, push to an array and then return that array at the end of the function. Also, instead of setting the object values to true (or false), set them to the number of occurrences the number has been found so far (and decrement the matching number when a match is found):

function problemOne_Solve() {
  const target = 17;
  const values = [11, 15, 3, 8, 2, 17, 0, 0, 17];
  const obj = {};
  const matches = [];
  for (const currNum of values) {
    const otherNum = target - currNum;
    if (obj[otherNum]) {
      obj[otherNum]--;
      matches.push([currNum, otherNum]);
    }
    obj[currNum] = (obj[currNum] || 0) + 1;
  }
  return matches;
}
console.log(problemOne_Solve());

And there is no such brackets after the if statement, which I thought was required.

Brackets are not required when there's a single statement after an if (or else if or else), eg:

if (true) console.log('true');
else console.log('this will not log');