CODEWITHSUNDEEP
arraysalgorithm
MarksCode
MarksCode

Reputation: 8604

2 unsorted arrays, find if any pairs of values add up to target?

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?

Upvotes: 2

Views: 109

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727137

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.

Upvotes: 1

stackoverflowuser2010
stackoverflowuser2010

Reputation: 41029

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.

Upvotes: 0

Related Questions