Find all missing numbers in an array

This is a popular array-based coding problem. Given an array with a range 0 - n-1 - the goal is to find all missing elements, but considering that the array can contain duplicate elements also.

The best solution IMO is to initialize a new array result[] with zeros that have the same size as the input array.

Iterate over the given array and mark each element in the given array marking that index as 1 in the array result[].

Now traverse the given array result[] from index arr[0] and print those indexes whose value is 0 as they are the elements that are missing in the given array.

Finding all missing numbers in an array - implementation

This is the solution when the array is unsorted and contains duplicate elements.

public class Main {

    public static void main(String[] args) {
        missingNumbers(new int[]{1, 1, 2, 3, 5, 5, 7, 9, 9, 9});
    }

    public static void missingNumbers(int[] arr) {
        int[] result = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            result[arr[i]] = 1;
        }

        for (int i = 1; i < result.length; i++) {
            if (result[i] == 0) {
                System.out.println("Missing number: " + i);
            }
        }
    }
}

Output:
Missing number: 4
Missing number: 6
Missing number: 8

For the sorted arrays and arrays that don't contain duplicates, the following is a very good solution:

public static void missingNumbers(int[] arr) {
    int current = 0;

    for (int i = arr[0]; i <= arr[arr.length - 1]; i++) {

        if (arr[current] == i) {
            current++;
        } else {
            System.out.println("Missing number: " + i);
        }
    }
}

That is all about how to find all missing numbers from an array in Java.