# Time complexity of obtaining the set of distinct elements in a sequence?

Consider a sequence $$s$$ of $$n$$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known about the worst-case time complexity of producing a sequence of all distinct elements in $$s$$, in any order?

By randomized hashing, one can do this in expected $$O(n)$$ time. On the upper bound side, one may sort the elements, then produce the output in a single pass by only copying elements which differ from their predecessors to the output - for a total time of $$O(n \log(n))$$.

But can one do better than $$O(n \log(n) )$$ deterministically?

Note: This is sort-of a "remove duplicates" problem, but since the order is not preserved I'm not sure it should be called that.

• There is an $\Omega(n\log n)$ lower bound on element distinctness (finding out whether all elements are distinct) in the comparison model. Does this answer your question? – Yuval Filmus Feb 21 '18 at 18:39
• I don't think we can ignore the specifics of the representation and computational model because sorting is known to be somewhat delicate and dependent on that -- for instance, Wikipedia seems to suggest it is known how to sort in $O(n \log n / \log \log n)$ time in some computational models, and even in $O(n (\log \log n)^2)$ time. So at least in some computational models that is a "yes one can do better" answer to your question. – D.W. Feb 21 '18 at 18:55
• @YuvalFilmus: Comparisons model, eh? I think perhaps not, since the hashing strategy, while non-deterministic, is not in the comparisons model. But +1 on that comment. – einpoklum Feb 21 '18 at 19:12
• When we have unbounded memory, $h(m)=m$ is a realizable hash function without conflict. The time-complexity is deterministic $O(n)$. (The space-complexity is $O(\max(a_i))$, where $\max(a_i)$ is the maximum of given numbers. Every time a larger number is read, we double the working space .) – John L. Jun 24 '19 at 19:16
• @einpoklum "The default value 0 for all elements is part of the particular RAM model" (that I defined). If you do not think that is a valid computation model at all, it is your choice. Note that for example all cells of a Turing machine are assumed to contain the blank symbol. That is (part of the reason) why I believe it is reasonable to include that in my computation model. By the way, we do not "finally read the entire array" since we will add an element $a_i$ to the set of distinct elements only when $arr[a_i]$ is changed from 0 to 1. So at the end, we will just return that set. – John L. Jun 25 '19 at 5:37