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');

Answer 2

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

If there is only one statement after if else the brackets becomes optional. Ideally you shouldn't write the if block is one line to make your code clean

As you are a beginner I would recommend you to use simple for loops instead of these fancy methods like find.

You can do that in following steps:

• Its clear that you need sum of each element with every other element of array. So you will need a nested loop structure
• The outer loop or main loop starts from 0 and loop till end of array.
• You need to create a inner loop or nested loop which starts from index after the current index.
• In the each iteration of nested loop you need to check if the sum of two elements is equal to requiredSum or not.

function pairWithSum(givenArray, requiredSum){
  for(let i = 0; i < givenArray.length; i++){
    for(let j = i + 1; j < givenArray.length; j++){
      let sum = givenArray[i] + givenArray[j];
      if(sum === requiredSum){
        return [givenArray[i], givenArray[j]];
      }
    }
  }
  return false
}

console.log(pairWithSum([1, 4, 5, 8], 12));
console.log(pairWithSum([1, 4, 5, 8], 15));

Answer 3

I'm wondering why it works

That is because, if expects an expression/ statement to validate.

values.find( (sum) => { return k-values[i] === sum} )

This is a statement and it will be evaluated before and its output will be passed to if for condition.

Now Array.find has a return type: T|<null> where T is any value array is made of. So in second iteration, when values[i] refers to 15, it will return 2.

Now in JS, 2 is a truthy value and hence it goes inside if block. Foe more reference, check All falsey values in JavaScript. Any value that is not in this list will be considered as true.

Answer 4

My Javascript solution using JS object. This solution memories the elements when we go through the array which can be memory expensive. But the complexity will stay as O(n).

const checkTwoSum = (arr, sum) => {
  const obj = {};
  const found = arr?.find(item => {
    const target = sum - item;
    if (obj[target]) return true;
    else {
        obj[item] = 1;
    }
  });

  return !!(found || found === 0);
}