How to Find All Numbers Disappeared in an Array? (C/C++ Coding Exercise)

Given an array of positive integers from 1 to n, where n is the size of the array, find the missing numbers if any numbers can only appear in the array at most twice.

For example, If the input is [1, 2, 2], the output should be [3].

Find Missing Numbers with O(n) space and O(n) time

With O(n) space, you can have another array or (Hash Set or unordered_set in C++) to record the existing numbers and the second iteration (from 1 to n) is simply to check the missing elements if it is not in the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        unordered_set<int> t;
        for (auto x: nums) {
            if (t.find(x) == t.end()) {
                t.insert(x); // store existing numbers
            }
        }
        vector<int> r;
        for (auto i = 1; i <= nums.size(); ++ i) {
            if (t.find(i) == t.end()) {
                r.push_back(i); // missing numbers not in the set
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        unordered_set<int> t;
        for (auto x: nums) {
            if (t.find(x) == t.end()) {
                t.insert(x); // store existing numbers
            }
        }
        vector<int> r;
        for (auto i = 1; i <= nums.size(); ++ i) {
            if (t.find(i) == t.end()) {
                r.push_back(i); // missing numbers not in the set
            }
        }
        return r;
    }
};

Find Missing Numbers with O(1) space and O(n) time

If the requirement is not to use any additional space (excluding return array or local simple variables), then you can only modify the input. The idea is to mark positive numbers visited by turning them into negatives in the desired locations. For example, if the input is, [3, 2, 2], then we iterative each number: 3 should be at index 2 (starting from 0), so it becomes [3, 2, -3], the next number is 2, so the input further becomes [3, -2, -3]. The next iteration pick the number -3, which does not change anything.

The second iteration finds the positive number(s), which represent the missing numbers (by its index plus 1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (auto i = 0; i < nums.size(); ++ i) {
            auto m = abs(nums[i]) - 1;
            nums[m] = -abs(nums[m]); // existing numbers now negative
        }
        vector<int> r;
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[i] > 0) {  // missing numbers are now positive
                r.push_back(i + 1);
            }
        }
        return r;
    }
};

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (auto i = 0; i < nums.size(); ++ i) {
            auto m = abs(nums[i]) - 1;
            nums[m] = -abs(nums[m]); // existing numbers now negative
        }
        vector<int> r;
        for (auto i = 0; i < nums.size(); ++ i) {
            if (nums[i] > 0) {  // missing numbers are now positive
                r.push_back(i + 1);
            }
        }
        return r;
    }
};

Generally O(1) space means, you can allocate memory (including local variables) but the memory allocated is not dependent on input size n and is a constant for all n. So if I allocate a local array variable of size n then it is not O(1) even though the variable is local. But the article above seems to be contradicting that. And no extra space means no allocation at all which means you shouldn’t be allocating local variables at all and must work on the input array itself.

“Without extra space” is vague. And in the article, it is said “in O(1) space”. Normally, we should not be allow to modify the input. The input should be read-only and O(1) space means that you just have a constant number of memory cells where you can read and write.

Without extra space means without allocating any extra memory. For example, one approach could be to create a new vector containing the set of numbers [1, n] and checking against the problem set to see which ones are missing. I’m not sure why you said the input has to be read only. O(1) space only means the memory requirements for the algorithm are constant, regardless of the size of the input.

–EOF (The Ultimate Computing & Technology Blog) —