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

Question

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?

Answer 1

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;
    }
}