Find All Numbers Disappeared in an Array

Problem

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.

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

Constraints

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

Solution

The problem Find All Numbers Disappeared in an Array can be solved by considering each array value as an index. By reallocating every given elements into their appropriate locations, elements that do not match their index at the end becomes the missing numbers.

Implementation

class Solution
{
  public:
    vector<int> findDisappearedNumbers(vector<int> &nums)
    {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        for (int i = 0; i < nums.size(); i++)
        {
            int num = nums[i];
            while (num != nums[num - 1])
                swap(num, nums[num - 1]);
        }

        vector<int> ret;
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] != i + 1)
                ret.push_back(i + 1);

        return ret;
    }
};