Python | Intersection of multiple lists

Given two list of lists, write a Python program to find the intersection between the given two lists. Examples:

Input : lst1 = [['a', 'c'], ['d', 'e']]
        lst2 = [['a', 'c'], ['e', 'f'], ['d', 'e']]
Output : [['a', 'c'], ['d', 'e']]

Input : lst1 = [[1, 5, 7], [2, 3], [6, 9], [4, 8]]
        lst2 = [[9, 3], [2, 3], [6, 9]]
Output : [[2, 3], [6, 9]]

  Approach #1 : Naive(List comprehension) The brute-force or naive approach to find the intersection of list of lists is to use List comprehension or simply a for loop. 

[['a', 'c'], ['d', 'e']]

Time complexity: O(n^2), where n is the length of the longest list among lst1 and lst2.

Auxiliary space: O(m), where m is the length of the intersection between lst1 and lst2.

 Approach #2 : Using Set intersection() This is an efficient method in comparison to the naive approach. We first convert both list of lists into list of tuples using map() because Python sets are compatible with tuples, not lists. Then we simply find Set intersection() of both the lists. 

[['d', 'e'], ['a', 'c']]

Time complexity: The program uses map() and set() functions, which have a time complexity of O(n). Therefore, the time complexity of this program is O(n), where n is the total number of elements in both input lists.

Auxiliary space: The program creates two temporary tuples (tup1 and tup2) to convert the inner lists of both input lists to tuples. The memory required to create these tuples is proportional to the total number of elements in both input lists. The program also creates a set to find the intersection of the two tuples. The memory required to create this set is proportional to the size of the smaller tuple. Finally, the program converts the resulting tuple back to a list using the map() function. The memory required for this conversion is proportional to the size of the resulting tuple. Therefore, the overall auxiliary space complexity of this program is O(n), where n is the total number of elements in both input lists.

 Approach #3 :  Using ‘&’

Using the & operator is a concise and efficient way to find the intersection of multiple lists in Python. This approach involves creating sets from the lists using the set() constructor and then using the & operator to find the intersection of the sets.

Here is an example of how you can use the & operator to find the intersection of two lists:

[['d', 'e'], ['a', 'c']]

The time and space complexity of the & operator approach for finding the intersection of multiple lists in Python will depend on the size of the lists and the characteristics of the elements they contain.

In general, the time complexity of the & operator is O(min(len(s), len(t))), where “s” and “t” are the sets being intersected. This means that it takes linear time to find the intersection, which makes it a relatively efficient approach for finding the intersection of sets. The space complexity is also O(min(len(s), len(t))), since it creates a new set to store the intersection.

Approach #4: Using Numpy

NumPy provides a wide range of mathematical operations and functions to work with arrays and matrices. We can use NumPy’s intersect1d() function to find the intersection of two or more lists.

• Define a function called intersection that takes two lists lst1 and lst2 as input.
• Convert lst1 and lst2 to numpy arrays arr1 and arr2 using np.array().
• Use the np.intersect1d() function to find the common rows between arr1 and arr2.
• Convert the resulting common rows to a numpy array common_rows.
• Convert common_rows back to a list of lists by using common_rows.view(arr1.dtype).reshape(-1, arr1.shape[1]).tolist() and assign it to result.
  Return result.

Here is the implementation of the Numpy approach:

Output:
[[‘a’, ‘c’], [‘d’, ‘e’]]

Time complexity: The time complexity of this approach is O(n log n), where n is the total number of elements in both input lists. This is because NumPy’s intersect1d function sorts the arrays and then performs a linear search to find common elements.

Auxiliary Space: The space complexity of this approach is O(m), where m is the size of the resulting list of common elements. This is because the function uses NumPy arrays to perform the intersection, and then converts the resulting array back to a list.