Skip to content

Instantly share code, notes, and snippets.

@jsphkhan
Last active June 23, 2018 16:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jsphkhan/7ff4b84d9eab7afb544fdb82e831ea58 to your computer and use it in GitHub Desktop.
Save jsphkhan/7ff4b84d9eab7afb544fdb82e831ea58 to your computer and use it in GitHub Desktop.
Given an array of numbers, find the 2 elements/numbers from the array that add up to a given sum
/*
eg. [1,2,3,9] Sum = 8, Output = -1 //not found
[1,2,4,4] Sum = 8, Output = 2,3 //found (return the index of matched elements)
Assumption - input array is sorted
This solution here is the fastest way, which is O(n) - linear time
*/
function findElementsThatAddToASum(arr, sum) {
var low = 0,
high = arr.length - 1;
while (low <= high) {
if(arr[low] + arr[high] === sum) {
return "Found: " + low + ", " + high; //found the 2 elements that add up to the sum
} else if(arr[low] + arr[high] < sum) {
low = low + 1;
} else {
high = high - 1;
}
}
return -1; //not found
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment