0
$\begingroup$

I have a list of millions of pairs of strings, and I want to join all of the pairs that have matching members into lists without duplicates.

Example input:

[["A", "B"],
 ["A", "D"],
 ["M", "Q"],
 ["A", "F"],
 ["D", "E"],
 ["Q", "Z"]]

Example output:

[["A", "B", "D", "E", "F"],
 ["M", Q", "Z"]]

Does anyone know of an efficient algorithm for this? I'm somewhat constrained by memory. Anything that would square the memory from the input would not be an option.

$\endgroup$
3
$\begingroup$

You can use a two pass approach:

In the first pass, identify all the different strings appearing in your input. (This can be done in various ways, e.g. hashing, trie, BST)

For the second pass initialize a Disjoint-set data structure with the strings found in the first pass and perform a union operation for each pair in the input.

$\endgroup$
  • $\begingroup$ You can do it in a single combined pass, too: build the hash table on the fly, and each time you see a new string, call MakeSet. This lets you process data in a streaming fashion (albeit with $O(n)$ memory). $\endgroup$ – D.W. Jun 4 '14 at 14:40

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.