Python | Intersection in Tuple Records Data

Sometimes, while working with data, we may have a problem in which we require to find the matching records between two lists that we receive. This is a very common problem and records usually occur as a tuple. Let’s discuss certain ways in which this problem can be solved. 

Method #1 : Using list comprehension List comprehension can opt as method to perform this task in one line rather than running a loop to find the common element. In this, we just iterate for single list and check if any element occurs in other one. 

The original list 1 is : [('gfg', 1), ('is', 2), ('best', 3)]
The original list 2 is : [('i', 3), ('love', 4), ('gfg', 1)]
The Intersection of data records is : [('gfg', 1)]

Time Complexity: O(n^2), where n is the length of the longer list. In the worst-case scenario where both lists have the same length, the time complexity will be O(n^2).

Auxiliary Space: O(k), where k is the number of common elements in both lists. This is because the result list res will only contain the common elements.

Method #2: Using set.intersection() This task can also be performed in smaller way using the generic set intersection. In this, we first convert the list of records to a set and then perform its intersection using intersection(). 

The original list 1 is : [('gfg', 1), ('is', 2), ('best', 3)]
The original list 2 is : [('i', 3), ('love', 4), ('gfg', 1)]
The Intersection of data records is : [('gfg', 1)]

Time complexity: O(m+n), where m and n are the lengths of test_list1 and test_list2 respectively. 
Auxiliary space: O(m+n), where m and n are the lengths of test_list1 and test_list2 respectively.

Method #3 : Using dict

This method creates two dictionaries from the input lists of tuples, finds the common keys between the two dictionaries, and creates a new list of tuples with the common keys and their corresponding values from the first dictionary.

The Intersection of data records is : [('gfg', 1)]

Time complexity: O(n)
Auxiliary Space: O(n)

Method #4 : Using List Comprehension and filter() function:

Algorithm:

1. Define two test lists of tuples – test_list1 and test_list2.
2.Use filter() function to filter out the tuples from test_list1 which are present in test_list2.
3. Return the filtered tuples as a list and store it in variable res.
4. Print the result.

The original list 1 is : [('gfg', 1), ('is', 2), ('best', 3)]
The original list 2 is : [('i', 3), ('love', 4), ('gfg', 1)]
The Intersection of data records is : [('gfg', 1)]

Time Complexity:

The filter() function has a time complexity of O(n) where n is the length of the iterable being filtered.
In the worst case, all tuples from test_list1 are compared with all tuples from test_list2, giving a time complexity of O(n^2).
Thus, the time complexity of the algorithm is O(n^2).
Auxiliary Space:

The auxiliary space of the algorithm is O(m), where m is the length of the filtered list.
In the worst case, all tuples from test_list1 are present in test_list2, giving a space complexity of O(n).
Thus, the space complexity of the algorithm is O(n).

Method 5 : using a loop to iterate through one of the lists and check if each element exists in the other list.

 Here is a step-by-step approach for this method:

1. Initialize an empty list called intersection.
2. Loop through each tuple in test_list1.
3. For each tuple, extract the first element (string) and check if it exists in test_list2 by looping through each tuple in test_list2 and comparing the first element of the tuple.
4. If the first element exists in test_list2, append the tuple from test_list1 to intersection.
5. Print the intersection list.

The intersection of data records is: [('gfg', 1)]

The time complexity of this method is O(n^2) because it requires iterating through both lists in a nested loop.

 The auxiliary space is O(k) where k is the number of common elements in both lists since we only store those common elements in the intersection list.

Method 6: Using the itertools module

1. Import the itertools module.
2. Use the itertools.product() function to create a Cartesian product of the two lists.
3. Use list comprehension to filter the resulting list to only include tuples where the first element of the tuple in test_list1 matches the first element of the tuple in test_list2.
4. Use list comprehension to extract the tuples from the resulting list that match the condition in step 3.
5. Assign the resulting list to the intersection variable and print it.

The intersection of data records is: [('gfg', 1)]

Time complexity: O(n)
Auxiliary space: O(n)

manjeet_04

Follow

Improve