Find All Numbers Disappeared in an Array

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.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

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

Output:
[5,6]

The intuition behind using a hash map is pretty clear in this case. We are given that the array would be of size N and it should contain numbers from 1 to N. However, some of the numbers are missing. All we have to do is keep track of which numbers we encounter in the array and then iterate from 1 …N1⋯N and check which numbers did not appear in the hash table. Those will be our missing numbers. 

But wait, that needs O(N) extra space to maintain the HashMap.

We definitely need to keep track of all the unique numbers that appear in the array. However, we don’t want to use any extra space for it. Here we can use the in place hashing technique used in First Missing Positive number in an Array

Walk along with the array. Change the sign of ath element if you meet a number a. Be careful with duplicates: do sign change only once. Use index 0  to save information about the presence of a number n since index n is not available.

Walk again along with the array. Return the index of the first positive element.

If nums[0] > 0 return n.

Algorithm

  1. Iterate over the input array one element at a time.
  2. For each element nums[i], mark the element at the corresponding location negative if it’s not already marked so i.e. nums[nums[i]−1]×−1 . Use nums[0] position to track for the n'th number. As we are interested to find the missing numbers between 1 to N only. And array indices are from 0 to n-1. So we can use the 0'th location to track the presence of n'th number in the array.
  3. Now, loop over numbers from 1⋯N , and for each number check if nums[i] is negative. If it is negative, that means we’ve seen this number somewhere in the array.
  4. Add all the numbers to the resultant array which don’t have their corresponding locations marked as negative in the original array.
  5. Add the n'th number in the array if nums[0] > 0
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        
        List<Integer> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        int n = nums.length;
        for(int i = 0 ; i < n ; i++){
            int k = Math.abs(nums[i]);
            if(k == n){
                nums[0] = - Math.abs(nums[0]);
            }else{
                nums[k] = - Math.abs(nums[k]);
            }
        }
        for(int i = 1 ; i < n ; i++){
            if(nums[i] > 0){
                result.add(i);
            }
        }
        if(nums[0] > 0){
            result.add(n);
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity : O(N)
  • Space Complexity : O(1) since we are reusing the input array itself as a hash table and the space occupied by the output array doesn’t count toward the space complexity of the algorithm.

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s