Given a list of list of integers how to find pair of lists which have overlapping i.e. 1 or more elements are common.
Is it possible to solve without having cartesian product of initial list with itself
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Build a hash of element -> list of lists that contain that element. From that it's easy to find all pairs of lists that share an element. Of course listing all pairs is still $O(n^2)$, since there might be quadratically many. But finding just $k$ pairs is $O(k+m)$, where $m$ is the total number of elements in all sets.