Python | Find missing elements in List

Sometimes, we can get elements in range as input but some values are missing in otherwise consecutive range. We might have a use case in which we need to get all the missing elements. Let’s discuss certain ways in which this can be done. 

Method #1 : Using list comprehension We can perform the task of finding missing elements using the range function to get the maximum element fill and then insert the elements if there is a miss. 

The original list : [3, 5, 6, 8, 10]
The list of missing elements : [0, 1, 2, 4, 7, 9]

Time Complexity: O(n) where m and n is the number of elements in the list. list comprehension performs n number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list

  Method #2 : Using set() This problem can also be performed using the properties of difference of set and then getting the elements that are missing in a range. 

The original list :[3, 5, 6, 8, 10]
The list of missing elements :[0, 1, 2, 4, 7, 9]

Time Complexity: O(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 difference() method of the set data type

Here is another alternative approach using the difference() method of the set data type to find missing elements in a list in Python:

The original list: [3, 5, 6, 8, 10]
The list of missing elements: [0, 1, 2, 4, 7, 9]

This approach has a time complexity of O(n), as it requires a single call to the difference() method on sets of size n. The auxiliary space is O(n), as a new set is created to store the missing elements.

Note: Like the previous approach, this approach will only find missing elements within the range from 0 to max_ele. If the list test_list contains elements outside of this range, they will not be included in the resulting list of missing elements. To find missing elements within a different range, you can adjust the arguments of the range() function accordingly.

Method#4: Using Recursive method.

The original list: [3, 5, 6, 8, 10]
The list of missing elements: [0, 1, 2, 4, 7, 9]

Time Complexity: O(n)

Auxiliary Space: O(n)

Method#5: Using NumPy module

step-by-step algorithm for implementing the approach:

1. Import the NumPy module.
2. Initialize the test_list with a list of integers.
3. Convert the test_list to a NumPy array using the np.array() function.
4. Find the maximum element in the test_array using the max() method.
5. Use NumPy’s arange() function to generate an array of numbers from 0 to max_element + 1.
6. Use NumPy’s setdiff1d() function to find the set difference between the generated array and the test_array.
7. Store the result in res.
8. Print the original list and the missing elements.

Output

The original list : [3, 5, 6, 8, 10]
The list of missing elements : [0 1 2 4 7 9]

Time Complexity:

• Finding the maximum element in the test_array takes O(n) time where n is the length of the test_array.
• Generating an array of numbers using arange() takes O(max_element) time.
• Computing the set difference using setdiff1d() takes O(max_element) time.
• Overall, the time complexity of the algorithm is O(max_element + n).

Auxiliary Space Complexity:

• Creating the NumPy array using np.array() takes O(n) space.
• Generating the array of numbers using arange() takes O(max_element) space.
• Computing the set difference using setdiff1d() takes O(max_element) space.
• Overall, the auxiliary space complexity of the algorithm is O(max_element + n).
• Note that this algorithm assumes that the list test_list contains non-negative integers. If the list contains negative integers or floats, the approach needs to be modified accordingly.

Method 6: Using the filter() function and the lambda function 

step-by-step algorithm for implementing the approach:

1. Define the function using a lambda function that takes an element x and checks if it is not in the my_list using the not in operator. This function will be used by the filter() function to filter out the elements that are not missing.
2. Use the filter() function and range(start_range, end_range+1) as arguments to filter out the missing elements from the range.
3. Convert the filtered result to a list using the list() function.
4. Return the list of missing elements.

[0, 1, 2, 4, 7, 9]

Time Complexity:

• The range of elements to be checked for is produced in O(1) time by the range() function.
• The lambda function in use by filter() checks whether such a missing element exists in O(1) time.
• The length of the range, n, specifies how long it’s going to take the filter() function to remove the missing elements.
• The filtered result is formed into a list in O(n) time by the list() function.
• As a result, this method has an overall time complexity of O(n), where n is just the length of the range.

Space Complexity:

Both the range() and the lambda functions used by filter() occupy O(1) space, therefore they do not add to the complexity of the entire space.

Method 7: Using the pandas Package-

Note: first install pandas by using – pip install pandas

• Creating a Dataframe from the test_list.
• Creating a range of numbers in the DataFrame.
• Performing merge on the dataframe and the range dataframe, filling the missing values.
• Filtering the DataFrame to show only the rows where the column value is missing.
• Finding the values from the DataFrame and converting them to a list.

Output

The original list : [3, 5, 6, 8, 10]
The list of missing elements : [0 1 2 4 7 9]

Time Complexity: O(N) where n is the length of the list, as it we have to traverse the whole list.

Space Complexity: O(N)  as we are creating a new pandas series of max length N.