[Solved] Find the intersection between sublists

by


Here is a more efficient algorithm:

  1. For each unique number that is present in at least one of the sublists, let’s maintain a list of indices of all sublists that contain this number. This part is O(n * log n) time if we use sorting to find unique numbers or O(n) if we use a hash table, where n is the total number of elements in all sublists.

  2. Let’s create a graph where vertices are sublist indices and an edge is present if two indices appear together in at least one list of indices among all numbers. We need create at most O(n) edges(this part is slightly non-trivial: there is no need to create all edges explicitly, we can just add an edge from an element to the next one in each sublist for all unique elements due to transitivity). Here is some pseudo code:

    g = empty graph
for elem in unique_elements:
    sublist_indices = list of indices of all sublists that contain this element
    for i = 1 ... size(sublist_indices - 1):
        g.add_edge(sublist_indices[i], sublist_indices[i + 1])

  3. Now we can find connected components in this graph using depth-first search in linear time(this graph is undirected).

  4. We know which sublists should be merged(they should be merged if and only if they are in the same connected component), so we can easily construct the answer.

The total time complexity is O(n). It is optimal because reading the input already requires O(n) operations.

5

solved Find the intersection between sublists