0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\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.♦ Jul 12 '18 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$ – Steven48 Jul 12 '18 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.♦ Jul 12 '18 at 3:14
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\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$ – Yuval Filmus Aug 12 '18 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 Aug 12 '18 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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