Pair of elements from a specified array whose sum equals a specific target number

I am in mid of my JavaScript session. Find this code in my coding exercise. I understand the logic but I didn’t get this map[nums[x]] condition.

function twoSum(nums, target_num) {  
    var map = [];  
    var indexnum = [];  

    for (var x = 0; x < nums.length; x++)  
    {  
        if (map[nums[x]] != null)  
        // what they meant by map[nums[x]]
        {  
            index = map[nums[x]];  
            indexnum[0] = index+1;  
            indexnum[1] = x+1;  
            break;  
        }  
        else  
        {  
            map[target_num - nums[x]] = x;  
        }  
    }  
    return indexnum;  
    }  
console.log(twoSum([10,20,10,40,50,60,70],50));

I am trying to get the Pair of elements from a specified array whose sum equals a specific target number. I have written below code.

function arraypair(array,sum){
        for (i = 0;i < array.length;i++) {
            var first = array[i];
            for (j = i + 1;j < array.length;j++) {
                var second = array[j];

                if ((first + second) == sum) {
            alert('First: ' + first + ' Second ' + second + ' SUM ' + sum);
            console.log('First: ' + first + ' Second ' + second);
                }
            }

        }
}

var a = [2, 4, 3, 5, 6, -2, 4, 7, 8, 9];

arraypair(a,7);

Is there any optimized way than above two solutions? Can some one explain the first solution what exactly map[nums[x]] this condition points to?

9 thoughts on “Pair of elements from a specified array whose sum equals a specific target number”

  1. function twoSum(arr, S) {
     const sum = [];
      for(let i = 0; i< arr.length; i++) {
        for(let j = i+1;  j < arr.length; j++) {
          if(S == arr[i] + arr[j]) sum.push([arr[i],arr[j]])
        }
      }
     return sum
    }
    

    Brute Force not best way to solve but it works.

    Reply
  2. Please try the below code. It will give you all the unique pairs whose sum will be equal to the targetSum. It performs the binary search so will be better in performance. The time complexity of this solution is O(NLogN)

    ((arr,targetSum) => {
        if ((arr && arr.length === 0) || targetSum === undefined) {
            return false;
        } else {
            for (let x = 0; x <=arr.length -1; x++) {
                let partnerInPair = targetSum - arr[x];
                let start = x+1;
                let end = (arr.length) - 2;
    
                 while(start <= end) {
                    let mid = parseInt(((start + end)/2));
                    if (arr[mid] === partnerInPair) {
                        console.log(`Pairs are ${arr[x]} and ${arr[mid]} `);
                        break;
                    } else if(partnerInPair < arr[mid]) {
                        end = mid - 1;
                    } else if(partnerInPair > arr[mid]) {
                        start = mid + 1;
                    }
                 }
            };
    
        };
    })([0,1,2,3,4,5,6,7,8,9], 10)
    
    Reply
  3. function twoSum(arr, target) {
        let res = [];
        let indexes = [];
        for (let i = 0; i < arr.length - 1; i++) {
            for (let j = i + 1; j < arr.length; j++) {
                if (target === arr[i] + arr[j] && !indexes.includes(i) && !indexes.includes(j)) {
                    res.push([arr[i], arr[j]]);
                    indexes.push(i);
                    indexes.push(j);
                }
            }
        }
        return res;
    }
    console.log('Result - ',
        twoSum([1,2,3,4,5,6,6,6,6,6,6,6,6,6,7,8,9,10], 12)
    );
    

    Brute force.

    Reply
  4. function twoSum(arr){
    
      let constant = 17;
    
      for(let i=0;i<arr.length-2;i++){
    
          for(let j=i+1;j<arr.length;j++){
    
              if(arr[i]+arr[j] === constant){
    
                  console.log(arr[i],arr[j]);
              }
          }
       }
    }
    
    Reply
  5. that map value you’re seeing is a lookup table and that twoSum method has implemented what’s called Dynamic Programming

    In Dynamic Programming, you store values of your computations which you can re-use later on to find the solution.

    Lets investigate how it works to better understand it:

    twoSum([10,20,40,50,60,70], 50)
    //I removed one of the duplicate 10s to make the example simpler
    

    In iteration 0:

    value is 10. Our target number is 50. When I see the number 10 in index 0, I make a note that if I ever find a 40 (50 – 10 = 40) in this list, then I can find its pair in index 0.

    So in our map, 40 points to 0.

    In iteration 2:

    value is 40. I look at map my map to see I previously found a pair for 40.

    map[nums[x]] (which is the same as map[40]) will return 0.
    That means I have a pair for 40 at index 0.
    0 and 2 make a pair.


    Does that make any sense now?

    Unlike in your solution where you have 2 nested loops, you can store previously computed values. This will save you processing time, but waste more space in the memory (because the lookup table will be needing the memory)

    Also since you’re writing this in javascript, your map can be an object instead of an array. It’ll also make debugging a lot easier 😉

    Reply
  6. Simple Solution would be in javascript is:

    var arr = [7,5,10,-5,9,14,45,77,5,3];
    var arrLen = arr.length;
    var sum = 15;
    
    function findSumOfArrayInGiven (arr, arrLen, sum){
      var left = 0;
      var right = arrLen - 1;
    
      // Sort Array in Ascending Order
      arr = arr.sort(function(a, b) {
        return a - b;
      })
    
      // Iterate Over
      while(left < right){
        if(arr[left] + arr[right] === sum){
          return {
              res : true,
              matchNum: arr[left] + ' + ' + arr[right]
          };
        }else if(arr[left] + arr[right] < sum){
          left++;
        }else{
          right--;
        }
      }
      return 0;
    }
    
      var resp = findSumOfArrayInGiven (arr, arrLen, sum);
    
      // Display Desired output
      if(resp.res === true){
        console.log('Matching Numbers are: ' + resp.matchNum +' = '+ sum);
      }else{
        console.log('There are no matching numbers of given sum');
      }
    

    Runtime test JSBin: https://jsbin.com/vuhitudebi/edit?js,console

    Runtime test JSFiddle: https://jsfiddle.net/arbaazshaikh919/de0amjxt/4/

    Reply
  7. Using HashMap approach using time complexity approx O(n),below is the following code:

    let twoSum = (array, sum) => {
        let hashMap = {},
          results = []
    
            for (let i = 0; i < array.length; i++){
                if (hashMap[array[i]]){
                    results.push([hashMap[array[i]], array[i]])
                }else{
                    hashMap[sum - array[i]] = array[i];
                }
              }
              return results;
        }
    console.log(twoSum([10,20,10,40,50,60,70,30],50));
    

    result:

    {[10, 40],[20, 30]}
    

    I think the code is self explanatory ,even if you want help to understand it,let me know.I will be happy enough to for its explanation.

    Hope it helps..

    Reply
  8. function sumOfTwo(array, sumNumber) {
      for (i of array) {
        for (j of array) {
            if (i + j === sumNumber) {
                console.log([i, j])
            }
        }
      }
    }
    sumOfTwo([1, 2, 3], 4)
    
    Reply
  9. function twoSum(args , total) {
        let obj = [];
        let a = args.length;
        for(let i = 0 ; i < a ; i++){
            for(let j = 0; j < a ; j++){
                    if(args[i] + args[j] == total) {
                        obj.push([args[i] , args[j]])
                    } 
    
            }
        }
        console.log(obj)}
    
    twoSum([10,20,10,40,50,60,70,30],60);
    /* */
    Reply

Leave a Comment