Finding the common elements between N lists in Java

Question

I need to write a Java program that finds the intersection (common elements) of an arbitrary number of lists or arrays of integers (of arbitrary length). I guess that Java Lists may have a useful method in order to achieve this, but I am taking a look at the API and can´t find it.

Any hint?

Answer 1

You can find the common elements between two lists by copying the elements of one list into a new list, and using retainAll:

List<T> commonElements = new ArrayList<>(list1);
commonElements.retainAll(list2);

This can be extended to n lists, since the common elements in n lists are the common elements of [the common elements of the first n-1 lists] and the [elements of the n-th list]:

commonElements.retainAll(list3);
commonElements.retainAll(list4);
...

e.g.

<T> List<T> commonElements(Iterable<? extends List<? extends T>> lists) {
  Iterator<? extends List<? extends T>> it = lists.iterator();
  List<T> commonElements = new ArrayList<T>(it.next());
  while (it.hasNext()) {
    commonElements.retainAll(it.next());
  }
  return commonElements;
}

Note that this will fail with a NoSuchElementException if lists is empty. It is straightforward to handle for this case, by adding a check for it.hasNext() before the first it.next().

Answer 2

You should think very carefully before using any of the methods retainAll, removeAll or containsAll with ArrayLists because contains for an ArrayList has O(n) time complexity. If a and b are both ArrayLists of length n, a.retainAll(b) has time complexity O(n^2). If you use a.retainAll(b) in a loop, the resulting algorithm quickly becomes completely impractical.

An alternative solution is to convert the ArrayLists to HashSets. contains for a HashSet has O(1) time complexity.

static <T> List<T> commonElements(Iterable<? extends List<? extends T>> lists) {
    Iterator<? extends List<? extends T>> it = lists.iterator();
    Set<T> commonElements = new HashSet<>(it.next());
    while (it.hasNext())
        commonElements.retainAll(new HashSet<>(it.next()));
    return new ArrayList<>(commonElements);
}

Of course, if there are a small number of short Lists, all the copying in the above code will make this version slower than @AndyTurner's. Which version you use depends on your exact situation.

Another problem with these solutions is how they deal with multiplicities. Suppose the first list is [1, 1, 1] and the second list is [1, 1]. The most reasonable interpretation for the intersection of these lists is [1, 1]. However, @AndyTurner's version will produce [1, 1, 1] and the above version will produce [1].

Here is a version that deals with multiplicities correctly. Method references and Map.merge require Java 8.

static <T> List<T> commonElements(Iterable<? extends List<? extends T>> lists) {
    Iterator<? extends List<? extends T>> iterator = lists.iterator();
    Map<T, Integer> multiplicities = count(iterator.next());
    while (iterator.hasNext()) {
        Map<T, Integer> listCount = count(iterator.next());
        for (Iterator<Map.Entry<T, Integer>> it = multiplicities.entrySet().iterator(); it.hasNext();) {
            Map.Entry<T, Integer> e = it.next();
            T key = e.getKey();
            Integer count = listCount.get(key);
            if (count == null)
                it.remove();
            else
                e.setValue(Math.min(count, e.getValue()));
        }
    }
    List<T> result = new ArrayList<>();
    for (Map.Entry<T, Integer> e : multiplicities.entrySet())
        result.addAll(Collections.nCopies(e.getValue(), e.getKey()));
    return result;
}

private static <T> Map<T, Integer> count(List<? extends T> list) {
    Map<T, Integer> result = new HashMap<>();
    for (T t : list)
        result.merge(t, 1, Integer::sum);
    return result;
}

You can test it as follows

List<Integer> list1 = Arrays.asList(1, 1, 2, 2, 2, 3, 4);
List<Integer> list2 = Arrays.asList(1, 1, 1, 2, 2, 3, 5);
List<Integer> common = commonElements(Arrays.asList(list1, list2));
System.out.println(common);

Output:

[1, 1, 2, 2, 3]

There are many ways to improve the above approach. For example, you could deal with the smallest List first to keep multiplicities as small as possible. Similarly, after computing listCount, you could swap listCount and multiplicities if listCount is smaller. Also you could replace the while by while (!multiplicities.isEmpty() && iterator.hasNext()) so that the algorithm stops immediately as soon as the intersection is found to be empty.