time complexity of erasing repeated entries

Question

This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be $n \log n$.

Problem

The input is a finite set $S$ and a finite list $T$ whose entries are in $S$. The size of the input is $n= |S|+ |T|$, where $|T|$ is the length of the list. The output is a list of the elements of $S$ that occur in the list $T$, an output list having no repeated elements of $S$. Does there exist a linear-time, $n p(\log n)$, where $p$ is a polynomial, or subquadratic-time algorithm for this problem?

I would be grateful for any ideas, direction, pseudo-code.

Answer 1

The basic algorithm is to first put all the members of S into a hash table $\mathcal{S}$. Then walk down the list T, recording its elements in a hash table $\mathcal{T}$ as you go. If an element has already been recorded in hash table $\mathcal{T}$ then you delete it from T. If an element does not appear in hash table $\mathcal{S}$ then you delete it from T. When you've completed your walk down T, there will be no repeated elements left in it and every remaining element will be a member of S.

Hash table insertions and lookups have amortized O(1) runtime so the whole algorithm scales O(n).