If I have m lists with n elements each, how would I go about finding duplicates in them (i.e. an element is in more than one of the lists)? My idea is to use hashing on the elements inside the list, which involves a O(1) hashing call on each of the elements and checking for collisions inside the buckets. However, on top of that, I would like to know which lists do not have any collisions with other lists (i.e. for each list, I would like to know with which other lists the intersection of their elements will be null). I am just wondering if another level of hashing is required, or perhaps using some other algorithms and data structures. Thanks.

  • $\begingroup$ Welcome to CS.SE! Can you pick just one problem statement, and edit the question to specify the algorithmic task more precisely? What are the inputs, and what are the desired outputs? I see about three different tasks here: (a) check whether there are any collisions, (b) check which lists have no collisions with any other list; (c) for each list, report which other lists it has collisions with. The site works best if you pick just one and ask about that. Different algorithms might be best for the different variants of this problem. $\endgroup$ – D.W. Mar 26 '17 at 23:29

Your Answer

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

Browse other questions tagged or ask your own question.