refactorized solve for an algorithm in javascript

I have attended a technical interview for a development company. They asked me the following:

Giving an array of numbers (n) find 2 numbers that sum gives (k) and print them.
e.g

Input: n = [2,6,4,5,7,1], k = 8   
Output: result=(2,6),(7,1)   

My solution:

function findSum(n,k){
    let aux = []
    for (let i = 0; i < n.length; i++) {
        for (let j = i+1; j < n.length; j++) {
            if (n[i] + n[j] == k) {
                aux.push({ first: n[i], second: n[j] })
            }
        }
    }
    return aux;
}

They told me that, it is possible to make the exercise with some kind of key or mapping.
Does some one know how to do it with only one loop?

7 answers

  • answered 2018-06-17 17:17 Máté Safranka

    A task like this can be as simple or as complicated as you want to make it. Here's one solution, for example:

    function findPairs(n, k) {
        return n.reduce((pairs, next, i) => pairs.concat(
            n.slice(i + 1)
                .filter(num => next + num === k)
                .map(num => [ next, num ])
            ),
            []
        );
    }
    

    For the inputs [2, 6, 4, 5, 7, 1] and 8 will output [ [2, 6], [7, 1] ].

  • answered 2018-06-17 17:17 Hawkins

    From https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/:

    1. Sort the array in non-decreasing order.
    2. Initialize two index variables to find the candidate elements in the sorted array. Initialize l to the leftmost index: l = 0, Initialize r to the rightmost index: r = n.length - 1
    3. Loop while l < r.
      1. if (n[l] + n[r] == k) then return 1
      2. else if( n[l] + n[r] < k ) then l++
      3. else r--
    4. No candidates in whole array - return 0

  • answered 2018-06-17 17:19 Vasily Liaskovsky

    Match a number x from array with a key Math.min(x, k - x). Then run through your array and store every number in a hash using mentioned key. When the key you are going to add already is in the hash - check if stored value and current number gives required sum.

    function findSum(n, k){
      let hash = {};
      for(let i = 0; i < n.length; ++i){
        let x = n[i], key = Math.min(x, k - x);
        if((key in hash) && hash[key] + x == k)
          return [hash[key], x];
        else hash[key] = x;
      }
    }
    

  • answered 2018-06-17 17:24 Onk_r

    I think by sorting you can do that

    var n = [2,6,4,5,7,1];
    var k = 8 ;
    n.sort();
    
    
    let start = 0, end = n.length-1;
    while(start < n.length && end >= 0) {
        let current_sum = (n[start] + n[end]);
        if(current_sum == k) {
            console.log('Found sum with '+ n[start] +' and '+ n[end]);
            break;
        }
        else if(current_sum > k) {
            end--;
        } else {
            start++;
        }
    }
    if(start == n.length || end < 0) {
        console.log('Not Found');
    }
    

    but while writing this code I got one another approach also

    const set = new Set([2,6,4,5,7,1]);
    var k = 8;
    let found = false;
    for (let item of set) {
        let another = k - item;
        if(set.has(another)){ 
            console.log('found with '+item +' and ' +another);
            found = true;   
            break;
        }
    }
    if(!found) {
        console.log('Not found');
    }
    

  • answered 2018-06-17 17:43 tevemadar

    If numbers are non-negative and the target value is within JavaScript array limit:

    function findsums(arr,k){
        var ret=[];
        var aux=[];
        arr.forEach(function(i){
          if(i<=k){
            if(aux[k-i])
              ret.push([k-i,i]);
            aux[i]=true;
          }
        });
        return ret;
    }
    
    console.log(findsums([2,6,4,5,7,1],8));

    Similar approach could work with a bitfield (or even with a sparse array of bitfields) too.

  • answered 2018-06-17 17:47 Andrew

    The key to solving a question like this with low time complexity is the ability to efficiently search the data structure. A lot of answers rearrange the array in a way where searching an array is optimized. Another approach is with a data structure that inherently has fast search.

    Set and Map data structures have O(1) time complexity for searches, which make them good data structures where searching can be leveraged to increase performance.

    I use a new Map and traverse the array while adding it as a key. I set the key to the number and the value to the number of times I see it. I use a map over a new Set because I can also keep track of the number of instances of that particular number.

    I search for the number that would sum up to k, which is: (k - num). If I find that number, I add both numbers to my results data structure and decrement the value by 1, to show that it's been used.

    Time complexity: O(n), memory complexity: O(2n). Twice the amount of space compared to the original array because I have a key and a value to store in my Map

    function pairSums(arr, k){
        const map = new Map
        const matches = []
        for (let num of arr) {
            const search = k - num 
            if (map.get(search) > 0) {
                matches.push([num, k - num])
                map.set(search, map.get(search) - 1)
            } else if (!map.has(num)){
                map.set(num, 1)
            } else {
                map.set(num, map.get(num) + 1)
            }
        }
        return matches
    }
    
    console.log(pairSums([2, 6, 6, 6, 2, 4, 4, 4, 5, 7, 1, 4, 2], 8))

  • answered 2018-06-17 19:13 Slai

    Minified alternative similar to @Andrew's great answer, but assumes that all numbers are above 0 :

    var pairs = (arr, k) => arr.reduce((a, n) => 
      (a[n - k]-- ? a.push([n, k - n]) : a[-n] = a[-n] | 0 + 1, a), []);
    
    console.log(JSON.stringify( pairs([2,6,4,5,7,1], 8) ));