I cannot figure out this problem even after 3 months since receiving it in my interview, and nobody I know has been able to solve it either. The full problem is:

Given two sorted arrays of integers (A and B) and an integer target, return true if and only if A[i] B[j]=target for some indices i and j. The algorithm must be O(logn) time and there aren't any space constraints.

I was able to come up with two solutions: a O(n) time and O(n) space one and an O(nlogn) time and O(1) space one. When trying to solve it in O(logn) time, I couldn't make much progress. I was thinking I could partition the arrays and treat it as a divide and conquer, but I was not sure how to select the subarrays given the target integer. Any help is greatly appreciated.

CodePudding user response：

This problem cannot be solved in faster than Θ(n) time in the worst case. Consider the following example input:

A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
B = [10, 20, 31, 40, 50, 60, 70, 80, 90, 100]
target = 111

The correct result is "true", since 80 31 = 111. Generalising from this example, we can imagine an input of this form where A contains the multiples of 10 and B contains the multiples of 10 except, possibly, one element of the form 10k   1. There is no way to tell whether B contains an element of the form 10k   1 without checking every element of B in the worst case, so even if we know that A and B are always in this form (a special case of the original problem), an algorithm cannot give a definitely-correct answer in sub-linear time.

So either the interviewer who posed this problem was mistaken, or something has been lost in communication and the problem given by the interviewer is not the same as the problem stated here.

CodePudding user response：

This is not possible. Without any guarantees about the numbers themselves (beyond their ordering), it is necessary to inspect all numbers individually, resulting in O(n) time complexity at best.

To prove this, assume you have an algorithm that returns True/False accordingly in O(log n) time. Let us pick an even number T as our target, and populate one of the lists with all even numbers 0 to (T-2). The other list, we'll initially populate with all the odd numbers 1 to (T-1). This way, two elements (one from each list) will never sum to our value T, because an odd number plus an even will never be even.

Now, the tricky part- we'll randomly select a number from the odd-list, and replace it with itself plus one. If we pick 3 from [1, 3, 5, 7, ...], we'd replace it with 4 for [1, 4, 5, 7, ...]. Now, this new even element will sum with a corresponding value in the even-list to make T, changing the answer from False to True. Our hypothetical algorithm would need to be able to detect this change in O(log n) time. However, I could have altered any of the odd values, and it would have absolutely zero effect on its neighbors and their placement in the original list. The only way to detect this change is to iterate over every single value in the odd list, and make sure they are all still odd.

Therefore, the best you can possibly achieve is O(n), since unless you inspect every value, I will be able to mutate the input in such a way that I change the outcome without your algorithm's detection.

CodePudding user response：

In case the answer is negative, you must look at all elements at least once to be sure, so the worst-case is indisputably O(n).

An easy O(n) time, O(1) space algorithm is possible by merging the sequences A[i] and target-B[LengthB-1-n] until you find equal elements.

E.g. (2, 3, 4, 5, 6, 8) and (0, 2, 8, 9) giving 9 is the same as a merge of (2, 3, 4, 5, 6, 8) and (0, 1, 7, 9).

CodePudding user response：

I think it's possible. If you consider the problem as searching a target value in a sorted matrix.

1. Every iteration, you have a M x N matrix m(m[i][j] = A[i] B[j]), and select the center value m[M/2][N/2].
2. Compared m[M/2][N/2] with target, you always exclude a M/2 x N/2 sub-matrix.
3. Search remaining 3 M/2 x N/2 sub-matrix repeatedly.

The algorithm complexity is O(log(m) log(n)), the base of log is 4/3, O(1) space.