efficient way to do 'contains' between two lists

Question

I have 2 lists of integers,

l1 = new ArrayList();
l2 = new ArrayList();

I want to find out duplicate items in both of them, I have my usual approach:-

for (Integer i : l1)
{
 if(l2.contains(i)){
    System.out.println("Found!");
  } 
}

I've heard contains() is O(n), making my implementation O(n^2).

Is there a better way to do this, (less than O(n^2)) ?

Answer 1

Sure - create a HashSet<Integer> from one of the lists first.

Set<Integer> set = new HashSet<Integer>(l2);
for (Integer i : l1) {
    if (set.contains(i)) {
        System.out.println("Found!");
    }
}

If you want to find all duplicate entries, you don't even need to write your own loop, as Set<E> provides everything you need...

Set<Integer> set = new HashSet<Integer>(l2);
set.retainAll(new HashSet<Integer>(l1));

Afterwards, set will be the intersection of the two lists.

Note that you can be even more efficient than this if both your lists are already sorted to start with. You just iterate over both at the same time, moving the "cursor" forward for whichever iterator currently has the smaller value.

Answer 2

The usual way is to add each item from the first list to a HashSet, and then test each item in the second list for existence in that set:

Set<Integer> firstSet = new HashSet<Integer>(l1);
for (Integer i : l2) {
    if (firstSet.contains(i)) {
        // Do stuff
    }
}