Find All Numbers Disappeared In An Array - Leetcode Solution

Problem statement:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array.

Example:

Input: [4,3,2,7,8,2,3,1]

Output: [5,6]

Solution:

One possible solution is to create a boolean array of size n+1 (since the array contains integers from 1 to n inclusive) and initialize all of its values to false, and then iterate through the input array and mark the corresponding index in the boolean array as true.

After that, iterate through the boolean array and add all indexes that are still false to a result array.

Here is the code for this approach:

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> result = new ArrayList<>();
    boolean[] seen = new boolean[nums.length+1]; //create boolean array
    
    //mark seen indexes as true
    for (int num : nums) {
        seen[num] = true;
    }
    
    //add unseen indexes to result array
    for (int i = 1; i < seen.length; i++) {
        if (!seen[i]) {
            result.add(i);
        }
    }
    return result;
}

Time complexity: O(n) Space complexity: O(n)

Note: This solution modifies the input array, which is usually not recommended in a coding interview. A more optimal solution that does not modify the input array could involve using negative numbers to mark seen indexes.

1