What is the best optimized way to find if a list contains every element of another list?

Question

I have two list:

List<String> firstList = new LinkedList<String>();
List<String> secondList = new LinkedList<String>();

I want to know if every element of a list is contained by the other list. A possible solution could be:

public boolean function(List<String> first, List<String> second)
{
first = firstList;
second = secondList
for (String item : firstList)
    {
            for (String elem : secondList)
            {
                if(elem.compareTo(item)!=0)
                return false;
            }
    }
 return true;
 }

As we can see, the time is quadratic. Is there a way to do it better?

Why not just use [`containsAll`](https://docs.oracle.com/javase/8/docs/api/java/util/List.html#containsAll-java.util.Collection-)? — resueman, Sep 19 '16 at 14:00
You can use one foreach for firstList and `contains` method of list. — Afsun Khammadli, Sep 19 '16 at 14:01
Your approach will often returns `false` when it should return `true`, because you return `false` too early. — Sergey Kalinichenko, Sep 19 '16 at 14:11

score 3 · Accepted Answer · edited May 23 '17 at 12:09

You have an O(n*m) implementation with O(1) space requirements; you could make an O(n+m) implementation with O(m) space requirements by adding elements of the first list to HashSet<String>, and then verifying that all elements of the second list are present:

Set<String> firstSet = new HashSet<String>(firstList);
for (String elem : secondList) {
    if(!firstSet.contains(item)) {
        return false;
    }
}
return true;

or even better

return new HashSet<>(firstList).containsAll(secondList);

(thanks, bradimus!)

Note: Your approach uses sub-optimal comparison mechanism: rather than calling compareTo, you could call equals, because you do not need to check if the word is alphabetically before or after.

Another problem is that your approach will often returns false when it should return true, because you return false too early.

Good observations on the OP's solution. I believe yours could be shortened to `return new HashSet<>(firstList).containsAll(secondList);` without loss of clarity. — bradimus, Sep 19 '16 at 14:48

score 1 · Answer 2 · edited Sep 19 '16 at 14:43

1

public boolean function(List<String> first, List<String> second) {
    return (second.size() == first.size() && first.containsAll(second))
}

edited Sep 19 '16 at 14:43

A M S Rejuan

447
6
12

answered Sep 19 '16 at 14:05

convexHull

1,761
2
15
18

This checks that the two lists contain *exactly the same elements*, not that the bigger list contains all elements of the smaller list. – Sir Celsius Sep 19 '16 at 14:13
@SirCelsius is right... But it is probably only the variation on `containsAll()` method usage... For bigger list it could be something like this `return first.size() >= second.size() ? first.containsAll(second) : second.contains(first)` – convexHull Sep 19 '16 at 14:22

score 0 · Answer 3 · answered Sep 19 '16 at 14:05

0

Depending on whether one or both lists change regulary you may find it more efficient to use HashSet<String> for one that changes rarely.

See Set operations: union, intersection, difference, symmetric difference, is subset, is superset for more details.

answered Sep 19 '16 at 14:05

OldCurmudgeon

64,482
16
119
213

score 0 · Answer 4 · answered Sep 19 '16 at 14:06

0

Try this:

!Collections.disjoint(list1, list2);

Or you can use containsAll

Hope it helps!

answered Sep 19 '16 at 14:06

score 0 · Answer 5 · edited May 23 '17 at 12:16

There is an existing answer that I believe can address your question.

The idea is basically to use two Set and to calculate the size of their intersection.

I believe that if you can afford to use Set instead of List so you can save time on contains. You will have a complexity of o(n) whatever happens.

Edit

If you care about matching duplicates in your input Lists the above solution may not be efficient. You may want to be careful about that.

score 0 · Answer 6 · answered Sep 19 '16 at 14:13

0

 return first.containsAll(second);

answered Sep 19 '16 at 14:13

Vikash Bhushan

1
1

What is the best optimized way to find if a list contains every element of another list?

6 Answers6