Efficient algorithm to determine if two sets of numbers are disjoint

algorithm, disjoint-sets

Solution

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

Problem

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. ```

Original source