Python | Find missing numbers in a sorted list range
Given a range of sorted list of integers with some integers missing in between, write a Python program to find all the missing integers.
Examples:
Input : [1, 2, 4, 6, 7, 9, 10] Output : [3, 5, 8] Input : [5, 6, 10, 11, 13] Output : [7, 8, 9, 12]
Method #1: List comprehension
# Python3 program to Find missing
# integers in list
def find_missing(lst):
max = lst[0]
for i in lst:
if i > max:
max = i
min = lst[0]
for i in lst:
if i < min:
min = i
list1 = []
for num in range(min + 1, max):
if num not in lst:
list1.append(num)
return list1
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
print(find_missing(lst))
Output
[3, 5, 8]
Time Complexity: O(N)
Auxiliary Space: O(1)
Method #2: List comprehension using zip()
# Python3 program to Find missing
# integers in list
def find_missing(lst):
return [i for x, y in zip(lst, lst[1:])
for i in range(x + 1, y) if y - x > 1]
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
print(find_missing(lst))
Output
[3, 5, 8]
Time Complexity: O(N)
Auxiliary Space: O(1)
Method #3: Using set The use of Python set is an efficient and tricky way to find the missing numbers in the list. We convert the list to set and simply output the difference between this set and a set that contains integers ranging from min(lst) and max(lst).
# Python3 program to Find missing
# integers in list
def find_missing(lst):
return sorted(set(range(lst[0], lst[-1])) - set(lst))
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
print(find_missing(lst))
Output
[3, 5, 8]
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
Method #4: Using difference() This is a similar approach to the previous one with a slight difference that instead of using ‘-‘ operator to find the difference between both the sets, we can use Python difference() method.
# Python3 program to Find missing
# integers in list
def find_missing(lst):
start = lst[0]
end = lst[-1]
return sorted(set(range(start, end + 1)).difference(lst))
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
print(find_missing(lst))
Output
[3, 5, 8]
Time Complexity: O(N)
Auxiliary Space: O(N)
Method#5: Using Recursive method.
# Function to find missing integers
def find_missing_recursive(lst, start, end):
if start > end:
return []
if start not in lst:
return [start] + find_missing_recursive(lst, start + 1, end)
return find_missing_recursive(lst, start + 1, end)
# Driver code
lst = [1, 2, 4, 6, 7, 9, 10]
start = lst[0]
end = lst[-1]
print(find_missing_recursive(lst, start, end))
#this code contributed by tvsk.
Output
[3, 5, 8]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#6: Using a dictionary to count the frequency of each integer in the list, then checking which integers are missing
def find_missing(lst):
# Create a frequency dictionary with keys ranging from the minimum to maximum value in the list
freq_dict = {i:0 for i in range(min(lst), max(lst)+1)}
# Iterate through the list and increment the frequency count for each value encountered
for i in lst:
freq_dict[i] += 1
# Return a list of all keys with frequency 0 (i.e., the missing values)
return [key for key, val in freq_dict.items() if val == 0]
# Example usage
lst = [1, 2, 4, 6, 7, 9, 10]
missing = find_missing(lst)
print("The original list: ", lst)
print("The missing elements: ", missing)
Output
The original list: [1, 2, 4, 6, 7, 9, 10] The missing elements: [3, 5, 8]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#7: Using set difference and itertools module:
Algorithm:
1.Define a function named ‘find_missing’ that takes a list as input.
2.Initialize a set that contains all integers between the minimum and maximum values of the input list.
3.Subtract the set containing the input list from the set created in step 2 to get the missing integers.
4.Sort the result and return it.
import itertools
def find_missing(lst):
return sorted(set(range(lst[0], lst[-1])) - set(lst))
lst = [1, 2, 4, 6, 7, 9, 10]
print("The original list: ", lst)
print("The missing elements: ", find_missing(lst))
#This code is contributed by Jyothi pinjala
Output
The original list: [1, 2, 4, 6, 7, 9, 10] The missing elements: [3, 5, 8]
Time Complexity:
The time complexity of this algorithm is O(n log n), where n is the length of the input list. The set operations take O(n) time in the worst case, and sorting the resulting set takes O(n log n) time.
Auxiliary Space:
The space complexity of this algorithm is O(n), where n is the length of the input list. This is because we are creating a set that contains all integers between the minimum and maximum values of the input list.
Method#7: Using numpy’s setdiff1d() function
Algorithm:
- Import the numpy library using import numpy as np
- Define a function find_missing that takes a list as input
- Convert the list to a numpy array using np.array(lst)
- Create a range of values between the minimum and maximum value in the list using np.arange(lst[0], lst[-1]+1)
- Use numpy’s setdiff1d() function to calculate the missing values between the full range and the converted array
- Convert the numpy array of missing values back to a list using missing.tolist()
- Return the list of missing values from the function
Call the function using a list as input - Print the original list and the missing elements list
#importing the numpy library
import numpy as np
def find_missing(lst):
# Converting the list to numpy array
arr = np.array(lst)
# Creating a range of values between the minimum and maximum value in the list
full_range = np.arange(lst[0], lst[-1]+1)
# Calculating the missing values using numpy's setdiff1d() function
missing = np.setdiff1d(full_range, arr)
# Converting the numpy array back to a list and returning it
return missing.tolist()
#Example usage
lst = [1, 2, 4, 6, 7, 9, 10]
missing = find_missing(lst)
print("The original list: ", lst)
print("The missing elements: ", missing)
Output:
The original list: [1, 2, 4, 6, 7, 9, 10]
The missing elements: [3, 5, 8]
Time Complexity: O(NlogN) (due to sorting in setdiff1d())
Auxiliary Space: O(N)
Contact Us