gistfile1.txt

Here is a solution using ES6 sets.

    var a = new Set(Array1);
    Array2.forEach(function(elem){
        a.delete(elem);
    });
    return a;

Here's the general idea of the algorithm:

• Iterate over Array1.
  • Add each item's className to a truth map
• Iterate over Array2
  • If the item's className is not in the truth map, add it to the result.

That simple, O(n+m). By a truth map, my intention is a plain js object, where each key is (in this case) a className, and each value is true.

That assumes that adding properties and removing properties from a JS object is O(1), but it works :)