# Compute pair of similar list from a collection of lists

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

• I can imagine some complex looping but not sure it would beat creating HashSets – paparazzo Feb 9 '17 at 12:20

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.