O (n) Algorithm to find if 2 arrays have 2 elements that add to the number

Question

I am studying an exam and stumbled upon this question which seems a bit complicated.

Let A [1 ... n] and B [1 ... n] be 2 arrays of integers, so that each element of A or B is in the range from 0 to m, where m = O (n). (I guess that means m <n?)

We need to develop an algorithm O (n) that finds two elements A [i] and B [j] such that A [i] + B [j] = a given number k. If they do not exist, we will send an error message.

Now sorting them is out of the question, since the best sorting algorithms are O (n lg n).

Maybe use a hash table .. Or just create a smaller array X of length m, so that each index counts the numbers of a number in A .. then we go through B .. calculate diff = k - B [j] .. and check X [diff] .. if it is greater than zero, then yes, it exists, then we could again go through A to find its index.

What do you guys think

Answer 1

m = O(n) means that m bounded by a constant multiple of n , not necessarily less than it.

What you can do is. Get an array of size k+1 (so the memory is O(m) , which is also O(n) ). Call this array C Initialize all values ​​as untagged, say -1. This is O(m) , which is also O(n) .

Now you know that k <= 2m , because A[i] and B[i] are <= m . So, you go through array A , mark all kA[i] in C , so C[kA[i]] = i (That is, if kA[i] >= 0 , if the indices begin with 0 ). This is O(n) . Then go through array B and for each B[j] check if C[B[j]] checked. If so, then C[B[j]] marks some index in A , where B[j]+A[C[B[j]]] = k . Going B and checking the label is also O(n) . If you do not find a match, there is no such pair.

The general algorithm is O(n) .

Here is an example:

 n = 5 m = 15 A = [1 7 4 2 10] B = [8 14 3 13 11] k = 20 

Going through A , you get:

 C: [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 1 -1 -1 2 -1 3 0 -1] 

(Interval for better visualization). Then you check B :

 B[0] -> C[8] -> -1 mismatch B[1] -> C[14] -> -1 mismatch B[2] -> C[3] -> -1 mismatch B[3] -> C[13] -> 1 match -> B[3] + A[1] = 20 

B[3] was 13, and A[1] was 7.

Answer 2

We will use a hash table containing the difference between each element in the first array and the sum. Basically just iterate over the first array, calculate the difference between the sum and each element of the array and store it in a hash table. Then iterate over the second array, checking whether each number is displayed in the hash table

Answer 3

You can sort in O (n) using the hash table method you described (you can just store the boolean instead of int, though, since you just need to know if it exists). In general, sort sorts are no better than O (n lg n), but if you know certain limitations you can do better (or if you can use sorts without comparison, such as radix sort (which I think you can also use here), mainly:

• Initialize an array A 'of size n and set all values ​​to false.
• For each element of A, set the corresponding index to 'in true.
• For each element in ', if the value is true, add the index to another array A' '.
• A '' is now sorted by A, with duplicate removal.
• Repeat for B.

Now the problem should be pretty trivial if you have sorting A and B.