Find Missing Elements

Concept Description

Finding multiple missing elements in a sorted array is an extension of finding a single missing element. Since the array is sorted, this task becomes straightforward. We can traverse the array and record any breaks in the sequence. The goal is to find all the numbers that are missing between the existing elements in the array.

Java Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import java.util.ArrayList;

public class Main {
    public static ArrayList<Integer> findMissingElements(int[] arr) {
        ArrayList<Integer> missing = new ArrayList<>();
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] + 1 != arr[i + 1]) {
                for (int j = arr[i] + 1; j < arr[i + 1]; j++) {
                    missing.add(j);
                }
            }
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 6, 7};
        System.out.println(findMissingElements(arr)); // Output should be [3, 5]
    }
}

C++ Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;

vector<int> findMissingElements(int arr[], int size) {
    vector<int> missing;
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] + 1 != arr[i + 1]) {
            for (int j = arr[i] + 1; j < arr[i + 1]; j++) {
                missing.push_back(j);
            }
        }
    }
    return missing;
}

int main() {
    int arr[] = {1, 2, 4, 6, 7};
    vector<int> missing = findMissingElements(arr, 5);
    for (int x : missing) cout << x << " ";  // Output should be 3 5
    return 0;
}

Python Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def find_missing_elements(arr):
    missing = []
    for i in range(len(arr) - 1):
        if arr[i] + 1 != arr[i + 1]:
            for j in range(arr[i] + 1, arr[i + 1]):
                missing.append(j)
    return missing

arr = [1, 2, 4, 6, 7]
print(find_missing_elements(arr))  # Output should be [3, 5]

In these examples, each code snippet defines a function that takes a sorted array as input. The function iterates through the array, checking for breaks in the sequence. If it finds a break, it fills in the missing elements and adds them to a list or vector, which it returns at the end.