Given N sorted arrays, check that there are two arrays that contains at least two common elements

Question

If you have N sorted arrays where possible elements are integers from 0~N-1, and elements in a single array are distinct, how do you check if there are at least two arrays such that at least two elements are common?

For example, if I have following arrays where N = 5:

A[0] = {0},
A[1] = {1, 3},
A[2] = {2},
A[3] = {1, 4},
A[4] = {1, 3}

then A[1] and A[4] both have 1 and 3 in common, and therefore the answer is true.

In other example where N is again 5:

A[0] = {0, 4},
A[1] = {1, 3},
A[2] = {1, 2, 4},
A[3] = {0, 3},
A[4] = {1}

No two arrays A[i], A[j] have at least two elements in common, therefore the answer is false.

It was part of an interview question, which I was only able to solve in O(n^3) time, by iterating through each combination of arrays(A[i], A[j]) and in each iteration I scan from 0 to N-1 to check there are two common elements.

The interviewer indicated that there is a faster solution, and kind of hinted that utilize sortedness of the arrays, but I wasn't able to come up with better solution even if I was thinking of this problem for last 24 hours.

What would be a faster algorithm than O(N^3) to solve this problem? Thank you.

Answer 1

Create graph with array vertices and number vertices (at most 2N vertices).
Connect every array vertice with its numbers.
If two arrays have a pair of common numbers, there is cycle with length=4 (B-1-C-2 at the picture)

Find if such cycle exists
Both creating graph and searching cycle takes O(N^2)

Answer 2

It's doable in O(n*m) with n = number of elements and m = number of arrays

pointers[m] // one pointer for every array starting at begin();
commons[m][m] = 0 // count commons for every array combination
while(any pointer != end() )
{
   find pointer with lowest value;
   if any other pointer has this value;
      common[x][y] ++; // increment the commons counter for the corresponding arrays
   increment chosen pointer;
}
where common[x][y] >= 2 -> arrays contain 2 or more common elements

The algorithm iterates over all arrays "at once" always continuing with the smallest element. This element is compared to the smallest not visited elements of the other arrays. If the element are equal a not is taken in the commons array to keep track of the number of common elements.

After every element was visited, you only have to look into the common matrix to see which arrays have more than two common elements.

EDIT: over read something in the question. Sorry