So given 2 unsorted arrays I have to find if any pairs of values (1 from each array) adds up to a target.
In javascript what I did was find the max and min values from array1, then make an array of size maxVal-minVal.
I then iterated over array1 and put a 1 at every index of the new array corresponding to the values of array1.
From then I looped through array2 and checked if newArray[ target - array2[i] ] == 1
Is this a good solution to this problem?
Yes, this is a good solution in terms of speed. However, this is not such a great solution in terms of space, because of this
make an array of size
maxVal-minVal
When maxVal-minVal is large, say, in hundreds of millions, you need to allocate and zero-initialize a very large array. If the two sets of numbers are relatively small, say, a few thousand items, the time it takes to initialize the array may exceed the time it takes to find the solution.
A better approach is to use a hash-based set container in place of an array, because you can run an algorithm without any changes, while memory requirements would be O(N), instead of O(maxVal-minVal).
In JavaScript, an object can be used as a hash-based container.
Suppose your two unsorted arrays have size M and N. You can run the following algorithm in O(M+N) using a HashSet (a set implemented as a hash table).
Iterate over the first array, and add each value into the HashSet.
Then iterate over the second array, where each item can be referenced as item[i]. Because you also know the target value T, you know that you are looking for T - item[i] from the first array. So for every item item[i] in the second array, look for the value T - item[i] in the HashSet. If you find such a value, then return true. Otherwise, if you exhaust all the item in the second array, then return false.
