matoski.com

Given an array of integers and a value, determine if there are any two integers in the array which sum equal to the given value.

Let’s see an example array that we can visualise it so we can come up with a proper approach.

[ 5, 6, 7, 1, 4, 2, 3 ]

We need to see if any 2 numbers create a sum of X. Let’s evaluate on a real case.

How we can solve this, we can use a hash set to store the values that can when added total to X, and we should also sort the array.

Algorithm

• Scan the whole array once and store the visit elements in a hash set.
• While scanning, for every element in the array we check if X - e is already visited
  • If X - e is found in the hash set, it means that there is a pair(e, X - e) in array whose sum is equal to the given value
  • If we have scanned all elements in the array and we didn’t find anything, return false

Solution with a hash set

let find_sum_of_two = function(A, X) {
    let values = new Set();
    for (let a in A) {
        if (values.has(X - A[a])) {
            return true;
        }
        values.add(A[a]);
    }
    return false;
}

let arr = [ 5, 6, 7, 1, 4, 2, 3 ];

console.log(arr, "has items with sum of", 5, find_sum_of_two(arr, 5));
console.log(arr, "has items with sum of", 10, find_sum_of_two(arr, 10));
console.log(arr, "has items with sum of", 11, find_sum_of_two(arr, 11));
console.log(arr, "has items with sum of", 20, find_sum_of_two(arr, 20));

And it should output

[ 5, 6, 7, 1, 4, 2, 3 ] 'has items with sum of' 5 true
[ 5, 6, 7, 1, 4, 2, 3 ] 'has items with sum of' 10 true
[ 5, 6, 7, 1, 4, 2, 3 ] 'has items with sum of' 11 true
[ 5, 6, 7, 1, 4, 2, 3 ] 'has items with sum of' 20 false

Runtime complexity: Linear O(n)

Memory complexity: O(n)

Solution

Let’s look at a solution that will allow us to improve a bit on the previous solution.

let find_sum_of_two = function(A, X) {
    let i = 0;
    let j = A.length - 1;

    while (i < j) {
        let sum = A[i] + A[j];
        if (sum == X) {
            return true;
        }

        if (sum < X) {
            i++;
        } else {
            j--;
        }
    }

    return false;

}

let arr = [1, 2, 3, 4, 5, 6, 7];

console.log(arr, "has items with sum of", 5, find_sum_of_two(arr, 5));
console.log(arr, "has items with sum of", 10, find_sum_of_two(arr, 10));
console.log(arr, "has items with sum of", 11, find_sum_of_two(arr, 11));
console.log(arr, "has items with sum of", 20, find_sum_of_two(arr, 20));

And it should output

[1, 2, 3, 4, 5, 6, 7] 'has items with sum of' 5 true
[1, 2, 3, 4, 5, 6, 7] 'has items with sum of' 10 true
[1, 2, 3, 4, 5, 6, 7] 'has items with sum of' 11 true
[1, 2, 3, 4, 5, 6, 7] 'has items with sum of' 20 false

Runtime complexity: Linear O(n), if we need to sort the array before we start then the complexity is O(nlogn)

Memory complexity: O(1)