Find Missing Elements - Unsorted

Concept Description

Finding missing elements in an unsorted array involves a bit more complexity compared to a sorted array. The aim remains the same: to find all elements that are missing from a sequence in the array. There are multiple methods to approach this problem, such as sorting the array first, using a hash set, or using a mathematical formula for a particular range of numbers. For simplicity, let’s consider sorting the array first and then finding the missing elements.

Java Example

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

public class Main {
    public static ArrayList<Integer> findMissingElements(int[] arr) {
        Arrays.sort(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 = {7, 2, 1, 6, 4};
        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
23
24
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> findMissingElements(int arr[], int size) {
    sort(arr, arr + 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[] = {7, 2, 1, 6, 4};
    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
11
def find_missing_elements(arr):
    arr.sort()
    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 = [7, 2, 1, 6, 4]
print(find_missing_elements(arr))  # Output should be [3, 5]

In these examples, the array is first sorted. The rest of the code is similar to the sorted array case. We iterate through the sorted array and identify the missing elements, which are then returned.