Find unique elements in the first list from two lists in Java

Question

I am trying to find unique elements in a main list by comparing it with another list with a time complexity better than O(mn). Ex:-

listA, listB . I want to get unique elements only in listA and add to a new list.

Here is what I did

for (String item : listA) {
 if (!listB.contains(item)) {
   newList.add(item)
 }
}

Here the time complexity is O(mn). Can anyone help me get to a better solution?

Possible duplicate of [Faster algorithm to find unique element between two arrays?](http://stackoverflow.com/questions/19203868/faster-algorithm-to-find-unique-element-between-two-arrays) — Ted, Aug 16 '16 at 19:38
Copy `listB` into a `HashSet` and do `setB.contains(item)`, then it is `O(m + n)`. — Andy Turner, Aug 16 '16 at 19:39
TC for HashSet.contains is O(1). Then how is tc for the code O(m+n) ? — Newbie, Aug 16 '16 at 19:59
@Newbie Copying `listB` to `setB` is O(m). Iterating over `listA` is O(n). — shmosel, Aug 16 '16 at 20:01

score 0 · Accepted Answer · answered Aug 16 '16 at 19:58

0

Set<String> setB = new HashSet<>(listB);
for (String item : listA) {
 if (!setB.contains(item)) {
    newList.add(item);
 }
}

Like @Andy Turner suggested. Here , Set.contains Time Complexity is O(1).

answered Aug 16 '16 at 19:58

Newbie

1 Answers1