# time complexity of erasing repeated entries

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.

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Also, where did you encounter this exercise? Can you credit the original source? And, can you tell us what concepts you have been learning in this part of the class/textbook? – D.W. Jul 12 '18 at 1:40
• This is not a hw question from a cs course. I'm on my own, learning, and have come across this problem in several contexts. – Steven48 Jul 12 '18 at 2:20
• Cool. I encourage you to identify the context where you came across it or credit the source? (I don't really care whether it's a homework or not; but if you saw it somewhere, it's appropriate to credit the source, and it's often helpful to know the context where you encountered it.) – D.W. Jul 12 '18 at 3:14

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.
• You can also use an old-style array of length $|S|$, to get a somewhat simpler algorithm running in linear time (modulo operations on the members of $S$). – Yuval Filmus Aug 12 '18 at 2:31