Find missing elements in a list created from a sequence of consecutive integers with duplicates in O(n)

user_612258 0
Viewed 1188

This is a Find All Numbers Disappeared in an Array problem from LeetCode:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

My code is below - I think its O(N) but interviewer disagrees

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    results_list=[]
    for i in range(1,len(nums)+1):
        if i not in nums:
            results_list.append(i)
    return results_list
python
4 Answers

You can implement an algorithm where you loop through each element of the list and set each element at index i to a negative integer if the list contains the element i as one of the values,. You can then add each index i which is positive to your list of missing items. It doesn't take any additional space and uses at the most 3 for loops(not nested), which makes the complexity O(3*n), which is basically O(n). This site explains it much better and also provides the source code.

edit- I have added the code in case someone wants it:

#The input list and the output list
input = [4, 5, 3, 3, 1, 7, 10, 4, 5, 3]
missing_elements = []

#Loop through each element i and set input[i - 1] to -input[i - 1]. abs() is necessary for 
#this or it shows an error
for i in input:    
    if(input[abs(i) - 1] > 0):
        input[abs(i) - 1] = -input[abs(i) - 1]
    
#Loop through the list again and append each positive value to output list
for i in range(0, len(input)):    
    if input[i] > 0:
        missing_elements.append(i + 1)
user_141061790

For me using loops is not the best way to do it because loops increase the complexity of the given problem. You can try doing it with sets.

def findMissingNums(input_arr):
    
    max_num = max(input_arr) # get max number from input list/array

    input_set = set(input_arr) # convert input array into a set
    set_num = set(range(1,max(input_arr)+1)) #create a set of all num from 1 to n (n is the max from the input array)

    missing_nums = list(set_num - input_set) # take difference of both sets and convert to list/array
    return missing_nums
    
input_arr = [4,3,2,7,8,2,3,1] # 1 <= input_arr[i] <= n
print(findMissingNums(input_arr)) # outputs [5 , 6]```
user_134168740

Use hash table, or dictionary in Python:

 def findDisappearedNumbers(self, nums):
     hash_table={}
     for i in range(1,len(nums)+1):
        hash_table[i] = False
     for num in nums:
        hash_table[num] = True
     for i in range(1,len(nums)+1):
        if not hash_table[i]:
           print("missing..",i)
user_85312150

Try the following :

a=input() #[4,3,2,7,8,2,3,1]
b=[x for x in range(1,len(a)+1)]
c,d=set(a),set(b)
print(list(d-c))
user_138274190
Related