Coding Challenge Speed Issue. Find elements from 2 arrays matching a given sum

Question

You have two integer arrays, a and b, and an integer target value v. Determine whether there is a pair of numbers, where one number is taken from a and the other from b, that can be added together to get a sum of v. Return true if such a pair exists, otherwise return false.

Example

For a = [1, 2, 3], b = [10, 20, 30, 40], and v = 42, the output is true because 40 + 2 = 42.

The above is my problem. I have the correct solution but I want a better way to write the solution...I want it to run faster. I'm currently using two for loops:

function sumOfTwo(a, b, v) {
    for(var i=0; i < a.length; i++) {
        for(var j=0; j < b.length; j++) {
            if(a[i] + b[j] === v) {
                return true;
            }
        }
    }
    return false;
}

Any Help is appreciated!

you can get lots faster depending on how large the arrays get — Keith Nicholas, Mar 09 '17 at 01:07
And not fast enough to solve it on this site: https://codefights.com/interview/qAL6AiSejoJZRNyox/description — Ryan, Mar 09 '17 at 01:10
http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number — epascarello, Mar 09 '17 at 01:13
You could use a binary search tree which could turn this from O(n^2) into O(nlog(n)) — Doug, Mar 09 '17 at 01:13

score 3 · Accepted Answer · answered Mar 09 '17 at 01:17

3

Turn one of the arrays into an array indexed by the values. Then loop through the other array, and test whether v - element is an element of the array.

function sumOfTwo(a, b, v) {
    var test = [];
    for (var i = 0; i < a.length; i++) {
        test[a[i]] = true;
    }
    for (var i = 0; i < b.length; i++) {
        if (test[v - b[i]]) {
            return true;
        }
    }
    return false;
}

answered Mar 09 '17 at 01:17

Barmar

669,327
51
454
560

this has hashing auto with using objects instead of array +1. try with `test ={}` – huseyin tugrul buyukisik Mar 09 '17 at 01:18

score 2 · Answer 2 · edited May 23 '17 at 12:10

You can achieve linear complexity if you first create a set from array a that will contain results of v - a[i]. This will take O(len(a)).

Then you iterate over b, and check if set.get(b), which is v - a[i], exists. If it does, then v - a[i] === b[i] so a[i] + b[i] === v. This will take O(len(b)).

The total complexity is thus O(len(a)) + O(len(b)) (checking existence in a set is O(1)).

From this follows that, if the arrays have equal lengths, the complexity is O(2N), which is O(N).

Here's the code:

function sumOfTwo(a, b, v) {
  const setOfRemaindersFromA = new Set(a.map(num => v - num));
  return b.some(num => setOfRemaindersFromA.has(num));
}

const a = [1, 2, 3, 4],
      b = [10, 20, 30, 40];
      
console.log(sumOfTwo(a, b, 42)); // true
console.log(sumOfTwo(a, b, 45)); // false

Note: Check out Barmar's answer for a pre-ES6 solution of this approach.

If the arrays can have different lengths, you have to build the set from the shorter one and iterate over the longer one to make sure all elements are covered.

Comparing array lengths is a constant operation so this doesn't affect the overall complexity.

function sumOfTwo(a, b, v) {
  const [shorter, longer] = a.length > b.length ? [b, a] : [a, b];
  const setOfRemaindersFromShorter = new Set(shorter.map(num => v - num));
  return longer.some(num => setOfRemaindersFromShorter.has(num));
}

const a = [1, 2],
      b = [10, 20, 30, 40];
      
console.log(sumOfTwo(a, b, 42)); // true
console.log(sumOfTwo(a, b, 45)); // false

score 2 · Answer 3 · answered Mar 09 '17 at 01:17

2

Thanks!! I tried the following:

function sumOfTwo(a, b, v) {
    var a = a.sort();
    var b = b.sort();
    for(var i=0; i < a.length; i++) {
        for(var j=b.length - 1; j >= 0; j--) {
           if(a[i] > v && b[j] < v) {
                break;
            }
            if(a[i] + b[j] === v) {
                return true;
            }
        }
    }
    return false;
}

Please let me know if I could improve that more!

answered Mar 09 '17 at 01:17

Ryan

63
6

my answer may be the slowest passing on average please check others performance too (epascarello and Barmar) – huseyin tugrul buyukisik Mar 09 '17 at 01:27

score 1 · Answer 4 · answered Mar 09 '17 at 01:23

Passed it with hashing and lookup

function sumOfTwo(a, b, v) {
    const x = a.reduce( (o,a) => { o[a]=1; return o; }, {})
    return b.some( b => { return x[v-b] })
}

If the arrays are sorted, could probably speed it up more to jump out of the loops if values are greater than v

score 0 · Answer 5 · answered Mar 09 '17 at 01:08

0

Checking with brute force is O(n*n)

Sort two arrays. Start from elements smaller than v and go to decreasing direction.(others will overflow for sure) Sorting can be O(nLogn)

 a ---> a'   O(nlogn)
 b ---> b'   O(nlogn)

binary search to elliminate a(i) > v and b(i)>v O(logn)

now you have much less values to continue as O(n*n)

answered Mar 09 '17 at 01:08

huseyin tugrul buyukisik

10,675
3
42
85

hey! benchmark Barmar's answer: . that could be faster with hashing with object instead of array. I didn't calculate worst case yet – huseyin tugrul buyukisik Mar 09 '17 at 01:20

Coding Challenge Speed Issue. Find elements from 2 arrays matching a given sum

5 Answers5