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

Question

I am studying for an exam and came across this question that seems a little tricky.

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

We need to design a O(n) algorithm 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 throw an error message.

Now Sorting them would be out of the question, as best sorting algorithms are O(n lg n) .

Maybe use a hash table .. Or just create a smaller array X of length m such that each index counts the occurrences 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 go through A again to find its index..

What do you guys think

Answer 1

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

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

Now you know that k <= 2m because A[i] and B[i] are both <= m. So you go through array A, mark in C all k-A[i], so C[k-A[i]] = i (That is if k-A[i] >= 0 assuming indices start from 0). This is O(n). Then go through array B and for each B[j] check if C[B[j]] has been already marked. If so, then C[B[j]] marks a certain index in A where B[j]+A[C[B[j]]] = k. Going over B and checking the mark is also O(n). If you don't find a match, there is no such pair.

Overall 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

After going over 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]

(Spacing is for better visualization) Then you check against 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 that contains the difference between each element in the first array and the sum. Basically just iterate through the first array, calculate the difference between the sum and each element of the array, and store it in the hash table. Then iterate through the second array, checking if each number appears in the hash table

Answer 3

You can sort in O(n) using the hash table method you described (you could just store a boolean instead of an int though since you just need to know if it exists). In general, comparison sorts are no better than O(n lg n) but if you know certain constraints you can do better (or if you can use non-comparison sorts like radix sort (which I think you can use here as well)). Basically:

1. Initialize an array, A', of size n and set all values to false.
2. For each element in A, set the corresponding index in A' to true.
3. For each element in A', if the value is true, append the index to another array A''.
4. A'' is now a sorted A, with duplicates removed.
5. Repeat for B.

The problem should be pretty trivial now that you have A and B sorted.