CODEWITHSUNDEEP
javalisttime-complexity
user840718
user840718

Reputation: 1611

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

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?

Upvotes: 1

Views: 1322

Answers (6)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

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.

Upvotes: 4

convexHull
convexHull

Reputation: 1881

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

Upvotes: 1

Sir Celsius
Sir Celsius

Reputation: 872

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.

Upvotes: 0

Vikash Bhushan
Vikash Bhushan

Reputation: 1

 return first.containsAll(second);

Upvotes: 0

user6503581
user6503581

Reputation:

Try this:

!Collections.disjoint(list1, list2);

Or you can use containsAll

Hope it helps!

Upvotes: 0

OldCurmudgeon
OldCurmudgeon

Reputation: 65813

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.

Upvotes: 0

Related Questions