Created
February 5, 2021 07:36
-
-
Save technikhil314/6d91cf0364498f2adfe9fe37b04627c2 to your computer and use it in GitHub Desktop.
Closest sum tuple from two arrays
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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); | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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