CODEWITHSUNDEEP
javaalgorithmlist
Meow
Meow

Reputation: 19071

How to avoid O(N^2) when comparing elements from 2 lists?

I have 2 lists with same Object type.

List A [ foo, bar, moo, woo, pee ]

List B [ bar, woo ]

I want to compare those 2 lists and if the name matches, set its property to true.

For instance,

if(ListA[1].name.equals(ListB[0].name)) { //match name 'bar' and 'bar'
    ListA[1].hasSameName = true;
}

something like that.

I can write O(N^2) solution.

for(Talent checkedTalent : ListA) {
    for(Talent filteredTalent : ListB) {
        if( checkedTalent.Id.equals(filteredTalent.Id) ) {
            filteredTalent.isSelected = true;   
        }
    }
}

Can this be done in more efficient way?

Upvotes: 3

Views: 3136

Answers (5)

no.good.at.coding
no.good.at.coding

Reputation: 20371

Notice that the O(n2) solution has that time-complexity because for each element from ListA, you must check all of ListB (again). You could reduce to O(n) if you could somehow do an O(1) lookup on ListB for the current element from ListA. One data structure that you can use to do that is a Map.

So, if you build a Map out of one of the lists and traverse the other, looking up each element in the Map to see if there is match, you can reduce the overall time complexity to O(n) - at the cost of O(n) space.

For example:

Map<String, Talent> map = new HashMap<String, Talent>();

for(Talent t : ListA)
{
    // traverse each talent into
    // a map element.
    map.put(t.id, t); 
}

for(Talent t : ListB)
{
    if(map.containsKey(t.id))
    {
        t.isSelected = true;
    }
}

Upvotes: 4

les2
les2

Reputation: 14479

You can create a Set from the first List:

Set mySet = new HashSet(listA);

Now you loop over listB:

for(Object foo : listB)
    if(mySet.contains(foo))
        foo.isSelected = true

This is O(n * lg n), I think, but I'm not going to provide a proof. :)

Upvotes: 1

jimmyorr
jimmyorr

Reputation: 11688

For some inspiration on how to do this more efficiently, read up on how a SQL join can be implemented, namely a Nested loop join, a Nested loop join with a b-tree index (sort one and binary search through it for each element in the other), a Merge join, or a Hash join. Same concept.

Upvotes: 1

aroth
aroth

Reputation: 54806

Use hashing for an O(n) solution (assuming an efficient hash implementation):

Set<String> ids = new HashSet<String>(ListA.size());
for(Talent checkedTalent : ListA) {
    ids.add(checkedTalent.Id);
}
for(Talent filteredTalent : ListB) {
    if (ids.contains(filteredTalent.Id)) {
        filteredTalent.isSelected = true;
    }
}

Upvotes: 5

corsiKa
corsiKa

Reputation: 82559

Sort then (2*(n log n)) and then walk your way along each list (2*n).

Upvotes: 3

Related Questions