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$.


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.

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Jul 12, 2018 at 1:40
  • $\begingroup$ 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. $\endgroup$
    – S. Seif
    Commented Jul 12, 2018 at 2:20
  • $\begingroup$ 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.) $\endgroup$
    – D.W.
    Commented Jul 12, 2018 at 3:14

1 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).

  • $\begingroup$ 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$). $\endgroup$ Commented Aug 12, 2018 at 2:31
  • $\begingroup$ To save some time, start with an empty hash table, iterate through the list, and if a list element is not in the hash table then add it, if it is in the hash table then remove it from the list. $\endgroup$
    – gnasher729
    Commented Aug 12, 2018 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.