# 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?

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] ]`.

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`

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;
}
}
``````

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) {
}
``````

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) {
}
``````

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.

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))``````

``````var pairs = (arr, k) => arr.reduce((a, n) =>