Find All Numbers Disappeared in an Array: Given an array nums of n integers where nums[i] is in the range [1,n], return an array of all the integers in the range [1,n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

Constraints:

• n == nums.length
• 1 <= n <= 10^5
• 1 <= nums[i] <= n

Try this Problem on your own or check similar problems:

1. Missing Number
2. Find All Duplicates in an Array
3. First Missing Positive

Solution:

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();
    int n = nums.length;
    for(int i = 0; i < nums.length; ++i){
        nums[(nums[i]-1)%n] += n;
    }
    for(int i = 0; i < nums.length; ++i){
        if(nums[i] <= n){
            res.add(i+1);
        }
    }
    return res;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

As in Missing Number the brute-force is trivial. We loop over range 1..n and check if the element exists in auxiliary (helper) data structure (for example set or boolean array with length n), if not just place it in the resulting array. However you will be asked to reduce the space complexity to constant O(1). How do we do that? Again we take a step back and think about properties of the array, we know that array should contain all elements from 1..n (in this case there are no missing numbers), if it doesn’t we have some repeating numbers in the input array.

The reframed question would be “can we use the input array to mark numbers we looped over and somehow distinguish between found number and missing numbers?” Since we know values are between 1..n (you can always ask the interviwer if this assumption is true and generally you get additional brownie points if you ask about the nature of input structure, is it ordered, what are the properties of numbers in array, can we assume order…), we can use this information each time we encounter a number we mark its correspoding index (e.g. you found number 4, mark the input array at index 3, assuming 0-index arrays). How do we mark the number? Well we can just add the array length to it because we know that will be the maximum value we can have (so we know if the value at certain index is larger than n, we have encountered the value that corresponds to the current index, index + 1). Note that we also can extract the frequency of each of the values, since the n (array length) value will be added as many times as we encountered the value in array (e.g if we have number 3 five times, the value at index 2 will be increased by 5n since we have number 3 five times).

But since we’re adding array length each time we have to take modulo of the current number to normalize it in the 1..n range (so we use (nums[i]-1)%n trick). In the second pass we loop over each element and check if the current value is <=n which means we couldn’t find the i+1 number in array so we store it in the array we return as result of our function.