You are given an unsorted list of 999,000 unique integers, each from 1 to 1,000,000. Find the missing 1000 numbers. What is the computational and space complexity of your solution?
Input: arr =[1,2,3,...,998999](missing 1000 random numbers from 1 to 1,000,000)Output: [list of 1000 missing numbers]Explanation: The output should be the 1000 numbers from 1 to 1,000,000 that are not present in arr.
Input: arr =[2,3,4,...,999001](missing 1 and 999002 to 1,000,000)Output: [1,999002,999003,...,1000000]Explanation: The missing numbers are the first and last 999 numbers in the range.
Since the range is known and the number of missing elements is small compared to the total, we can use a boolean array to mark which numbers are present. Then, we scan for unmarked indices to find the missing numbers.
classSolution {
public List<Integer>findMissingNumbers(int[] arr) {
int n = 1000000;
boolean[] present =newboolean[n + 1];
for (int num : arr) present[num]=true;
List<Integer> ans =new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!present[i]) ans.add(i);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
classSolution:
deffind_missing_numbers(self, arr: list[int]) -> list[int]:
n =1000000 present = [False] * (n +1)
for num in arr:
present[num] =True ans = []
for i in range(1, n +1):
ifnot present[i]:
ans.append(i)
return ans
We can use a set to store all numbers in the input, then iterate through the range and collect numbers not in the set. This is more memory-efficient if using a hash set.
classSolution {
public List<Integer>findMissingNumbersSet(int[] arr) {
int n = 1000000;
Set<Integer> s =new HashSet<>();
for (int num : arr) s.add(num);
List<Integer> ans =new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!s.contains(i)) ans.add(i);
}
return ans;
}
}
1
2
3
4
5
classSolution:
deffind_missing_numbers_set(self, arr: list[int]) -> list[int]:
n =1000000 s = set(arr)
return [i for i in range(1, n +1) if i notin s]