Efficient Intersection of Two List<String> in Java

Efficient intersection of two ListString in Java?

You can use retainAll method:

columnsOld.retainAll (columnsNew);

More efficient way to get the intersection between 2 or more nested ArrayLists

The intersection of two lists is done using the retainAll() method.

It update the list, so if you don't want that, you should copy the list first.

If you have more than 2 lists, you copy the first and then call retainAll() for each of the remaining lists.

ArrayList<ArrayList<String>> lists = ...

List<String> intersection = new ArrayList<>(lists.get(0));
for (List<String> list : lists.subList(1, lists.size()))
    intersection.retainAll(list);

However performance will be a bad O(n*m), where n and m are the sizes of the two largest lists.

That is because retainAll() does a contains() against the list given in the parameter, which is a sequential search, for each element in the intersection list.

Performance can be improved to O(n), where n is the largest list, by converting the lists to sets.

List<String> intersection = new ArrayList<>(lists.get(0));
for (List<String> list : lists.subList(1, lists.size()))
    intersection.retainAll(new HashSet<>(list));

In Java 8+, the for loop can be simplified to one of these:

lists.subList(1, lists.size()).stream().map(HashSet::new).forEach(intersection::retainAll);

lists.subList(1, lists.size()).forEach(list -> intersection.retainAll(new HashSet<>(list)));

Intersection and union of ArrayLists in Java

Here's a plain implementation without using any third-party library. Main advantage over retainAll, removeAll and addAll is that these methods don't modify the original lists input to the methods.

public class Test {

    public static void main(String... args) throws Exception {

        List<String> list1 = new ArrayList<String>(Arrays.asList("A", "B", "C"));
        List<String> list2 = new ArrayList<String>(Arrays.asList("B", "C", "D", "E", "F"));

        System.out.println(new Test().intersection(list1, list2));
        System.out.println(new Test().union(list1, list2));
    }

    public <T> List<T> union(List<T> list1, List<T> list2) {
        Set<T> set = new HashSet<T>();

        set.addAll(list1);
        set.addAll(list2);

        return new ArrayList<T>(set);
    }

    public <T> List<T> intersection(List<T> list1, List<T> list2) {
        List<T> list = new ArrayList<T>();

        for (T t : list1) {
            if(list2.contains(t)) {
                list.add(t);
            }
        }

        return list;
    }
}

Most efficient way to find unique intersections from two different ArrayLists?

Add all the categoryIDs from ListA to a Set, let's call it setACategories. Afterwards, loop through ListB, if setACategories contains the categoryID of an element from ListB then add that element of ListB to results.

results should also be a Set, because it looks like you only want one match from listB to go into results and not multiple matches (allows you to avoid the call to (!results.contains(itemB)).

Intersection of two lists by object property

Similarly to Eran's answer above but perhaps with slightly more efficiency you could pull the IDs out into a separate Set first:

Set<String> ids = list2.stream().map(obj -> obj.id).collect(Collectors.toSet());

List<MyObject> intersect = list1.stream()
    .filter(obj -> ids.contains(obj.id))
    .collect(Collectors.toList());

The reason this would be more efficient is that for each item in list1 you can determine if the ID is in list2 in O(1) time so overally your runtime is O(list1 + list2)

Java 8 Lambda - Intersection of Two Lists

The simplest approach is this:

List<T> intersect = list1.stream()
                         .filter(list2::contains)
                         .collect(Collectors.toList());

What is the efficient algorithm / way to find intersection between 2 array lists. ( I am using java 8 )

List<T> intersect = list1.stream()
    .filter(list2::contains)
    .collect(Collectors.toList());

CREDIT: Fat_FS answer at Intersection and union of ArrayLists in Java.

Make sure you override equals and hashcode methods (assuming you wanted to look at the contents of the objects for equality comparison)

Convert list to set for better performance

---

Related Topics