Python | Uncommon elements in Lists of List

This particular article aims at achieving the task of finding uncommon two list, in which each element is in itself a list. This is also a useful utility as this kind of task can come in life of programmer if he is in the world of development. Lets discuss some ways to achieve this task.

Method 1 : Naive Method 
This is the simplest method to achieve this task and uses the brute force approach of executing a loop and to check if one list contains similar list as of the other list, not including that. 

The original list 1 : [[1, 2], [3, 4], [5, 6]]
The original list 2 : [[3, 4], [5, 7], [1, 2]]
The uncommon of two lists is : [[5, 6], [5, 7]]

Time Complexity: O(n), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the list “test_list”.

 Method 2 : Using set() + map() and ^ 
The most efficient and recommended method to perform this task is using the combination of set() and map() to achieve it. Firstly converting inner lists to tuples using map, and outer lists to set, use of ^ operator can perform the set symmetric difference and hence perform this task. Further if it is required to get in lists of list fashion, we can convert outer and inner containers back to list using map().

The original list 1 : [[1, 2], [3, 4], [5, 6]]
The original list 2 : [[3, 4], [5, 7], [1, 2]]
The uncommon of two lists is : [[5, 6], [5, 7]]

Time Complexity: O(n*n) where n is the number of elements in the string list. The set() + map() and ^  is used to perform the task and it takes O(n*n) time.
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the test list.

Method 3 : Using list comprehension and set intersection:

Algorithm:

1. Initialize two lists, test_list1 and test_list2
2. Initialize an empty list res_list to store the uncommon elements
3. Use a list comprehension to iterate through each element in test_list1, and check if it is not in test_list2. If it is not, append it to res_list
4. Use another list comprehension to iterate through each element in test_list2, and check if it is not in test_list1.
5. If it is not, append it to res_list
6. Print the res_list

The original list 1 : [[1, 2], [3, 4], [5, 6]]
The original list 2 : [[3, 4], [5, 7], [1, 2]]
The uncommon of two lists is : [[5, 6], [5, 7]]

Time Complexity:
The time complexity of this code is O(n^2), where n is the length of the longer list. This is because the ‘not in’ operation requires iterating through the entire list to check if the element is present.

Space Complexity:
The space complexity of this code is also O(n^2), since we are creating a new list to store the uncommon elements, and this list could potentially be as large as the input lists.

manjeet_04

Follow

Improve