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]

Solution: Hash map

We can easily solve this problem by using a hash map to store the appearance of each element. And then we use another loop to check for every element.

vector<int> findDisappearedNumbers(vector<int>& nums) {
    unordered_map<int, int> table;
    for(int i=0; i<nums.size(); i++) {
        table[nums[i]] = i;
    }

    vector<int> result;
    for(int i=1; i<=nums.size(); i++) {
        if(table.find(i) == table.end()) {
            result.push_back(i);
        }
    } 
    return result;
}

Solution: Without extra space

The basic idea here is to label all appeared numbers in the array. Since we don’t want to introduce extra space and given all numbers are positive(from 1 to n), negate the value in the corresponding position is one choice.

vector<int> findDisappearedNumbers(vector<int>& nums) {
    for (int i=0; i<nums.size(); i++) {
        int index = abs(nums[i]) - 1;
        nums[index] = nums[index] > 0 ? -nums[index] : nums[index];
    }

    vector<int> ans;
    for (int i=0; i<nums.size(); i++) {
        if (nums[i] > 0) ans.push_back(i+1);
    }
    return ans;
}