Python – Split heterogeneous type list

Sometimes, we might be working with many data types and in these instances, we can have a problem in which list that we receive might be having elements from different data types. Let’s discuss certain ways in which this task can be performed.

Method #1 : Using list comprehension + isinstance() 
The combination of above both functionalities can be used to perform this task. In this, we just extract the similar element types using different list comprehensions and detect the type using isinstance().

The original list : ['gfg', 1, 2, 'is', 'best']
Integer list : [1, 2]
String list : ['gfg', 'is', 'best']

Time Complexity: O(n*n), where n is the length of the input list. This is because we’re using list comprehension + isinstance() which has a time complexity of O(n*n) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of string list.

 
Method #2 : Using defaultdict() + loop 
This is yet another way in which this problem can be solved. In this, we initialize the list as data type for defaultdict() and loop through each element and save each datatype list in defaultdict.

The original list : ['gfg', 1, 2, 'is', 'best']
Integer list : [1, 2]
String list : ['gfg', 'is', 'best']

Time Complexity: O(n*n), where n is the length of the list test_list 
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list 

Method #3: Using filter() and lambda function

Use the filter() function with a lambda function to split the heterogeneous list into two lists containing only integers and strings, respectively.

Step-by-step approach:

• Initialize the original list.
• Use the filter() function with a lambda function to create two lists, one containing only integers and the other containing only strings.
• Convert the filtered objects into lists.
• Print the resulting integer and string lists.

Below is the implementation of the above approach:

The original list : ['gfg', 1, 2, 'is', 'best']
Integer list : [1, 2]
String list : ['gfg', 'is', 'best']

Time complexity: O(n), where n is the length of the original list. Therefore, the overall time complexity of this method is O(n).
Auxiliary space: O(n) because two new lists are created to store the filtered elements.

Method #4:  Using  recursive method :

Algorithm:

1. Define a function split_list(lst) that takes the input list lst as an argument.
2. If the length of the input list lst is 0 or 1, then return the input list as it is since there is no need to split it further.
3. Otherwise, split the input list lst into two parts by creating two empty lists res_int and res_str.
4. Iterate over each element elem in the input list lst.
5. If the current element elem is an integer, then append it to the res_int list.
6. If the current element elem is a string, then append it to the res_str list.
7. Recursively call the split_list() function with the first half of the input list as the argument and store the
8. returned result in a variable left_list.
9. Recursively call the split_list() function with the second half of the input list as the argument and store the
10. returned result in a variable right_list.
11. Concatenate left_list and right_list to get the final result and return it.

The original list : ['gfg', 1, 2, 'is', 'best']
Integer list : [1, 2]
String list : ['gfg', 'is', 'best']

Time Complexity :
The time complexity of this  depends on the number of elements in the input list lst and the number of recursive calls made to the split_list() function. In the worst case, the input list is split into two equal halves at each recursive call, resulting in a total of log n recursive calls, where n is the number of elements in the input list. At each recursive call, we iterate over each element of the input list once. Therefore, the time complexity of this algorithm is O(n * log n), where n is the number of elements in the input list.

Auxiliary Space:
The space complexity of this  depends on the number of recursive calls made to the split_list() function. In the worst case, the input list is split into two equal halves at each recursive call, resulting in a total of log n recursive calls, where n is the number of elements in the input list. Each recursive call creates two new lists res_int and res_str, which can each hold up to n/2 elements. Therefore, the space complexity of this algorithm is O(n * log n), where n is the number of elements in the input list.