Find Missing 1000 Numbers in Large Range

Problem

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?

Examples

Example 1

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.

Example 2

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.

Example 3

Input: arr = [1, 2, 3, ..., 999000] (missing 1,000,001 to 1,000,000)
Output: [999001, 999002, ..., 1000000]
Explanation: The last 1000 numbers are missing.

Solution

Method 1 – Boolean Array Marking

Intuition

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.

Approach

1. Create a boolean array of size 1,000,001 (index 0 unused).
2. For each number in the input list, mark its index as present.
3. Scan the boolean array from 1 to 1,000,000 and collect indices that are not marked.
4. Return the list of missing numbers.

Code

C++

class Solution {
public:
    vector<int> findMissingNumbers(vector<int>& arr) {
        int n = 1000000;
        vector<bool> present(n + 1, false);
        for (int num : arr) present[num] = true;
        vector<int> ans;
        for (int i = 1; i <= n; ++i) {
            if (!present[i]) ans.push_back(i);
        }
        return ans;
    }
};

Go

func FindMissingNumbers(arr []int) []int {
    n := 1000000
    present := make([]bool, n+1)
    for _, num := range arr {
        present[num] = true
    }
    ans := make([]int, 0, 1000)
    for i := 1; i <= n; i++ {
        if !present[i] {
            ans = append(ans, i)
        }
    }
    return ans
}

Java

class Solution {
    public List<Integer> findMissingNumbers(int[] arr) {
        int n = 1000000;
        boolean[] present = new boolean[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;
    }
}

Python

class Solution:
    def find_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):
            if not present[i]:
                ans.append(i)
        return ans

Complexity

• ⏰ Time complexity: O(n) where n = 1,000,000, as we scan the array and mark each number.
• 🧺 Space complexity: O(n) for the boolean array.

Method 2 – Set Difference

Intuition

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.

Approach

1. Insert all numbers from the input list into a set.
2. Iterate from 1 to 1,000,000 and collect numbers not in the set.
3. Return the missing numbers.

Code

C++

class Solution {
public:
    vector<int> findMissingNumbersSet(vector<int>& arr) {
        int n = 1000000;
        unordered_set<int> s(arr.begin(), arr.end());
        vector<int> ans;
        for (int i = 1; i <= n; ++i) {
            if (!s.count(i)) ans.push_back(i);
        }
        return ans;
    }
};

Go

func FindMissingNumbersSet(arr []int) []int {
    n := 1000000
    s := make(map[int]struct{}, len(arr))
    for _, num := range arr {
        s[num] = struct{}{}
    }
    ans := make([]int, 0, 1000)
    for i := 1; i <= n; i++ {
        if _, ok := s[i]; !ok {
            ans = append(ans, i)
        }
    }
    return ans
}

Java

class Solution {
    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;
    }
}

Python

class Solution:
    def find_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 not in s]

Complexity

• ⏰ Time complexity: O(n) for building the set and scanning the range.
• 🧺 Space complexity: O(n) for the set.