So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time complexity faster than O(N log N)? So I'm going to go into what I've been pondering, but have a couple specific questions at the bottom.
Comparision based So the baseline case would just be to compare every element in array_a against every element in array_b, being O(N^2). So what I was thinking was using a sort O(N log N), and then iterating through each of the arrays, making comparing array[i] with array[i+1], if they are not equal, copy array[i] to a new array (or a linked list, since I'd just be accessing it in order for the next step) and then increment i, so that way I have arrays without duplicates. Then do a preliminary check to see whether the # of elements are the same in both lists. Then with the list, compare whether the first element in the linked lists are equivalent, then check the next node in the linked list, and so on. If all checks are equal then they represent the same set. So this would be O(N log N). Doing a sort with a tree might work as well, but again would still be in the same complexity class of O(N log N)...
Hashing? So what I was thinking initially was looking at using hashsets to remove duplicates since operations with those would be amortised constant time, doing a preliminary check by checking whether both arrays have the same amount of distinct elements, adding the hashes of the elements of both arrays if they are not equal then there's no point in checking every element of each array and comparing it so that way a response of false would be relatively quick, if they are equal, then to check against collisions I'd sort it and then check arr_1[i] with arr2_[i] for i = 0, ..., n-1 - so the step of sorting would be the slowest giving this a time complexity of O(n log n) based on the sorting function used.
Questions Other than using hashing-based structures or algorithms that would require elements to be sorted first,, what other data structures (like trees would work I'd supposed) could I use to remove duplicates in an efficient way? Are there any novel data structures (even if impractical in practice) or different approaches for removing duplicates?
If the only information known about the sets is that they have a total order relation, would this make any impact on whether each element can be hashed and the quality of the hashes on a theoretical point of view?
Are there any properties in set theory that I could exploit somehow for a faster algorithm design in a language-agnostic way?
