Javascript optimization for pair search algorithm
I am working on a javascript function that takes an array of integers and a target as arguments. The challenge is to find the first pair of integers in the array that sum to the target. I've tried this in a few different ways, but I keep getting timeout error for large input arrays. Can someone please give me some pointers on how best to optimize this code? Thank!
var sum_pairs = function(ints, s){
var r = [];
var a = true;
var l = ints.length;
for(var j = 0; j < l; j++){
if(a){
for(var i = 0; i < j; i++){
if(ints[j] + ints[i] == s){
r[0] = ints[i];
r[1] = ints[j];
a = false;
break;
}
}
}
else{
console.log('breaking');
break;
}
}
return r[0] == null ? null : r;
}
source to share
You can use some acceleration mechanisms like
- single cycle,
- hash table for visited values
- variable
a
for elementarray[i]
- very short variable names (just kidding)
The long list needs 153ms .
var sum_pairs = function (array, s) {
var a, i,
hash = Object.create(null);
for (i = 0; i < array.length; i++) {
a = array[i];
if (hash[s - a]) {
return [s - a, a];
}
if (!hash[a]) {
hash[a] = true;
}
}
};
console.log(sum_pairs([11, 3, 7, 5], 10)); // [3, 7]
console.log(sum_pairs([4, 3, 2, 3, 4], 6)); // [4, 2]
console.log(sum_pairs([0, 0, -2, 3], 2)); // undefined
console.log(sum_pairs([10, 5, 2, 3, 7, 5], 10)); // [3, 7]
console.log(sum_pairs([1, 2, 3, 4, 1, 0], 2)); // [1, 1]
console.log(sum_pairs([1, -2, 3, 0, -6, 1], -6)); // [0, -6]
console.log(sum_pairs([0, 2, 0], 0)); // [0, 0]
console.log(sum_pairs([5, 9, 13, -3], 10)); // [13, -3]
.as-console-wrapper { max-height: 100% !important; top: 0; }
source to share
For each number we encounter while iterating through the array, add that expected partner number target - number
to Set
. As soon as we come across a number that is already in our set, we know that his partner has already met and returned this pair as a solution:
// Return the first two values of 'numbers' summing up to 'target':
function sum_pairs(numbers, target) {
let paired = new Set();
for (let number of numbers) {
if (paired.has(number)) return [target - number, number];
paired.add(target - number);
}
}
// Examples:
console.log(...sum_pairs([9, 3, 7, 5, 1], 10)); // [3, 7]
console.log(...sum_pairs([4, 3, 2, 3, 4], 6)); // [4, 2]
console.log(...sum_pairs([9, 3, 6, 4, 1], 10)); // [6, 4]
This implementation has the complexity of a linear runtime and is therefore faster for long input arrays, but it has additional memory cost.
If you're going to use raw speed, replace for-loop with the traditional for-loop binding and let
with a declaration var
.
source to share