Efficient algorithm to determine if two sets of numbers are disjoint

Question

Practicing for software developer interviews and got stuck on an algorithm question.

Given two sets of unsorted integers with array of length m and other of 
length n and where m < n find an efficient algorithm to determine if 
the sets are disjoint. I've found solutions in O(nm) time, but haven't 
found any that are more efficient than this, such as in O(n log m) time.

Answer 1

Using a datastructure that has O(1) lookup/insertion you can easily insert all elements of first set.

Then foreach element in second set, if it exists not disjoint, otherwise it is disjoint

Pseudocode

function isDisjoint(list1, list2)
    HashMap = new HashMap();
    foreach( x in list1)
        HashMap.put(x, true);

    foreach(y in list2)
        if(HashMap.hasKey(y))
             return false;
    return true;

This will give you an O(n + m) solution

Answer 2

Fairly obvious approach - sort the array of length m - O(m log m). For every element in the array of length n, use binary search to check if it exists in the array of length m - O(log m) per element = O(n log m). Since m<n, this adds up to O(n log m).