Skip to content

Instantly share code, notes, and snippets.

@technikhil314
Created February 5, 2021 07:36
Show Gist options
  • Save technikhil314/6d91cf0364498f2adfe9fe37b04627c2 to your computer and use it in GitHub Desktop.
Save technikhil314/6d91cf0364498f2adfe9fe37b04627c2 to your computer and use it in GitHub Desktop.
Closest sum tuple from two arrays
// O(a+b) := O(2n) := O(n)
function optimizedFindClosestSumTupple(arr1, arr2, requiredSum) {
const map = new Map();
let minDiff = Number.MAX_VALUE;
const result = [];
arr1 = arr1.sort((a, b) => a - b > 0 ? 1 : -1);
arr2 = arr2.sort((a, b) => a - b > 0 ? 1 : -1);
for (let l = 0, r = arr2.length - 1; l < arr1.length && r >= 0;) {
const sum = arr1[l] + arr2[r];
const diff = Math.abs(sum - requiredSum);
if (diff < minDiff) {
minDiff = diff;
}
map.set([arr1[l], arr2[r]], diff);
if (sum > requiredSum) {
r--;
} else {
l++;
}
}
map.forEach((val, key) => {
if (val === minDiff) {
result.push(key);
}
})
return result;
}
const arr1 = [4, 3, 7, 5, 1, -10];
const arr2 = [10, 20, 25, 40, 33];
const requiredSum = 16;
const optimizedResult = optimizedFindClosestSumTupple(arr1, arr2, requiredSum);
console.log(optimizedResult);
// O(aXb) := O(n^2)
function findClosestSumTupple(arr1, arr2, requiredSum) {
const map = new Map();
let minDiff = Number.MAX_VALUE;
const result = [];
arr1.forEach(a => {
arr2.forEach(b => {
const diff = Math.abs(requiredSum - (a + b));
map.set([a, b], diff);
if (diff < minDiff) {
minDiff = diff;
}
})
})
map.forEach((val, key) => {
if (val === minDiff) {
result.push(key);
}
})
return result;
}
const arr1 = [4, 3, 7, 5, 1, -10];
const arr2 = [10, 20, 25, 40, 33];
const requiredSum = 16;
const result = findClosestSumTupple(arr1, arr2, requiredSum);
console.log(result);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment