If N sorted arrays are specified, check for two arrays containing at least two common elements

Question

If you have N sorted arrays, where the possible elements are integers from 0 ~ N-1, and the elements in one array are different, how can you check if there are at least two arrays, for example, at least two elements?

For example, if I have the 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 correct.

In another 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, so the answer is false.

This was part of an interview question that I could only solve O (n ^ 3) times by repeating each combination of arrays (A [i], A [j]) and at each iteration I scan from 0 to N-1 to check the presence of two common elements.

The interviewer indicated that there is a faster solution, and there is a hint that uses sorting arrays, but I could not find a better solution, even if I thought about this problem in the last 24 hours.

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

Answer 1

Create a graph with the vertices of the array and numerical vertices (no more than 2N vertices).
Connect each vertex of the array with its numbers.
If two arrays have a pair of common numbers, then there is a cycle with length = 4 (B-1-C-2 in the figure)

Find if such a cycle exists.
Both graph and search cycles take O (N ^ 2)

Answer 2

This is possible 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 the smallest element. This element is compared with the smallest elements not visited by other arrays. If the element is equal, then the commons array does not accept a value to track the number of common elements.

After each element has been visited, you only need to look into the common matrix to see which arrays have more than two common elements.

EDIT: read something on this question. Unfortunately