0

I need to create a function that take as parameter an array and a target. It should return an array of arrays where the sum of these numbers equals to the target

sumPairs(array, target) {

}

For example:

sumPairs([1, 2, 3, 4, 5], 7) // output : [[2, 5], [3, 4]]

I know I have to use map(), and probably reduce(), set(), or filter() maybe (I read their documentation in MDN but still cant find out). I tried some ways but I can't get it.

If you guys could help me to find out how to dynamically create arrays and push them into a new array..

I read there some solutions (Split array into arrays of matching values) but I hate to just use created functions without knowing what they really do or how they work.

Yoël Zerbib
  • 177
  • 2
  • 10
  • I mean, I don't know how many arrays will be needed to push into the newArray, maybe reduce() can help if you have any solution (and explaination because if not I won't learn from the solution) – Yoël Zerbib Oct 10 '20 at 13:23
  • The sub arrays can only have 2 items or you must yield a minimum/maximum number if arrays? – plalx Oct 10 '20 at 14:05
  • The exercise says that it sould be arrays of pairs that sum the target value so I think only 2 items – Yoël Zerbib Oct 10 '20 at 14:09
  • You can achieve this in linear time instead of quadratic time like the selected answer. – plalx Oct 10 '20 at 14:37

3 Answers3

2

Some very basic code for achieving it, Just run all over combinations and conditionally add the items you want.

function sumPairs(array, target) {
  var res = [];
  for(var i = 0; i < array.length; i++){
    for(var j = 0; j < array.length; j++){
      if(i!=j && array[i]+array[j]==target && 
      res.filter((x)=> x[0] == array[j] && x[1] == array[i]).length == 0 )
        res.push([array[i], array[j]]);
    }
  }
  return res;
}

var result = sumPairs([1, 2, 3, 4, 5], 7);
console.log(result);

Option 2 - see this answer for more options (like using reduce)

function sumPairs(array, target) {
  return array.flatMap(
    (v, i) => array.slice(i+1).filter(w => (v!=w && v+w==target)).map(w=> [w,v])
  );
}

var result = sumPairs([1, 2, 3, 4, 5], 7);
console.log(result);
Asaf
  • 1,446
  • 9
  • 17
  • Thank you thousands times ! Need to practice my logic of thinking !! – Yoël Zerbib Oct 10 '20 at 14:00
  • I'm struggling to understand the Option 1, how i & j will be different at a point of time ? – Yoël Zerbib Oct 10 '20 at 14:10
  • Can you explain more what the first Option does ? – Yoël Zerbib Oct 10 '20 at 14:12
  • At least just the condition you used in first Option lol – Yoël Zerbib Oct 10 '20 at 14:22
  • The condition is checked if the numbers not in the same index in the array, and if the numbers sum is 7, also for duplication detction the last condition: if there is already array with reverse order not add it. To clarify this last condition, this will fix the problem of this result [2,5],[5,2] – Asaf Oct 10 '20 at 14:34
  • @Asaf Please also note that if the array is **already sorted**, then vanshaj's solution would be best and be linear time as well. – plalx Oct 10 '20 at 15:23
  • How i & j wont be the same index of the array if both of them start at 0 and take ++ every time ? – Yoël Zerbib Oct 10 '20 at 18:17
  • 1
    No, for example: in the first iteration of both the array[0] === array[0]... – Asaf Oct 10 '20 at 18:22
  • Thank you so much, now just last thing, could you put the last condition in older syntax ? cause with arrow and the && in the middle of the condition it's hard for me to understand.. – Yoël Zerbib Oct 11 '20 at 11:16
  • res.filter(function (x) { return x[0] == array[j] && x[1] == array[i]; }); But still I don't understand this condition – Yoël Zerbib Oct 11 '20 at 11:22
  • If the current array includes [2, 5] and the next added pair is [5, 2] skip, so we add only unique pairs. – Asaf Oct 11 '20 at 12:02
  • Okay but what is the . lengths == 0 at the end of the condition ? – Yoël Zerbib Oct 11 '20 at 17:17
1

"The exercise says that it sould be arrays of pairs that sum the target value so I think only 2 items"

If you need a pair that matches a sum and you pick any number from the list, you are left with the following equation to solve num + x = sum where we want to find x. E.g. if you picked 7 and the target sum is 10 then you know you are looking for a 3.

Therefore, we can first construct a counting map of the numbers available in our list linear (O(n)) time and then search for matches in linear time as well rather than brute forcing with a quadratic algorithm.

const nums = [1, 2, 3, 4, 5];

console.log(findSumPairs(nums, 7));

function findSumPairs(nums, sum) {
  const countByNum = countGroupByNum(nums);
  
  return nums.reduce((pairs, num) => {
    countByNum[num]--; 
    const target = sum - num;
    
    if (countByNum[target] > 0) {
      countByNum[target]--;
      pairs.push([num, target]);
    } else {
      countByNum[num]++;
    }
    
    return pairs;
  }, []);
}

function countGroupByNum(nums) {
  return nums.reduce((acc, n) => (acc[n] = (acc[n] || 0) + 1, acc), {});
}

Here's another implementation with more standard paradigms (e.g. no reduce):

const nums = [1, 2, 3, 4, 5];

console.log(findSumPairs(nums, 7));

function findSumPairs(nums, sum) {
  const countByNum = countGroupByNum(nums);
  const pairs = [];

  for (const num of nums) {
    const target = sum - num; //Calculate the target to make the sum
    countByNum[num]--; //Make sure we dont pick the same num instance

    if (countByNum[target] > 0) { //If we found the target
       countByNum[target]--;
       pairs.push([num, target]);
    } else {
       countByNum[target]++; //Didin't find a match, return the deducted num
    }
  }

  return pairs;
}

function countGroupByNum(nums) {
  const countByNum = {};

  for (const num of nums) {
    countByNum[num] = (countByNum[num] || 0) + 1;
  }

  return countByNum;
}
plalx
  • 42,889
  • 6
  • 74
  • 90
  • (Btw your answer is heping me more than the previous marked answer, just changed that) – Yoël Zerbib Oct 10 '20 at 14:41
  • I'll re-write a second implementation without reduce. – plalx Oct 10 '20 at 14:42
  • 1
    The second implementation superHelped me to understand the reasoning ! Now I'm gonna try to understand with the reduce() method. Thank you so much for your help ! – Yoël Zerbib Oct 10 '20 at 15:06
  • I'm meeting a problem when the sum should be 0 and there is a list like so: [6, -6, 8, -8, 1, 9, -10, 0, 0] I get [ [ 6, -6 ], [ 8, -8 ], [ 0, 0 ], [ 0, 0 ] ] instead of [ [ 6, -6 ], [ 8, -8 ], [ 0, 0 ]] – Yoël Zerbib Oct 10 '20 at 15:44
  • 1
    Okay I just added a condition to the if (countByNum[target] should also be > 0) – Yoël Zerbib Oct 10 '20 at 16:24
  • @YoëlZerbib Yeah I missed that edge case. Second implementation also had the else condition wrong where `--` was used instead of `++` to put back the non-used num. – plalx Oct 10 '20 at 18:48
0

You can also sort your array and find all the pairs with given sum by using two pointer method. Place the first pointer to the start of the array and the second pointer to the end.

if the sum of the values at the two places is :

  1. More than target: Decrement your second pointer by 1
  2. Less than target: Increment your first pointer by 1
  3. Equal to target: This is one possible answer, push them to your answer array and increment your first pointer by 1 and decrement your second pointer by 1.

This is more performant solution with complexity O(n*log(n))

vanshaj
  • 499
  • 1
  • 4
  • 13