Find All Numbers Disappeared in an Array easy

Problem Statement

Given an array nums of integers between 1 and n (inclusive), where n is the length of the array, find all the numbers that are missing from the array.

Example 1

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

Example 2

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

Steps

The core idea is to use the array itself as a hash table. We can utilize the fact that the numbers are within the range [1, n]. We'll use the array index as the key and the value as the number at that index. We'll manipulate the array to mark the presence of a number.

  1. Iterate through the array: For each number num in nums, we'll find its corresponding index ( num - 1 because indexing starts from 0). We then mark the presence of this number by making the element at that index negative. If the element at the index is already negative, it means the number has been encountered before.

  2. Find missing numbers: Iterate through the array again. If an element is positive, it means the corresponding number (index + 1) is missing. Add it to the result list.

Explanation

Let's trace Example 1:

nums = [4,3,2,7,8,2,3,1]

  1. Iteration 1: num = 4. Index = 3. nums[3] becomes -7. nums = [4, 3, 2, -7, 8, 2, 3, 1]
  2. Iteration 2: num = 3. Index = 2. nums[2] becomes -2. nums = [4, 3, -2, -7, 8, 2, 3, 1]
  3. Iteration 3: num = 2. Index = 1. nums[1] becomes -3. nums = [4, -3, -2, -7, 8, 2, 3, 1]
  4. Iteration 4: num = 7. Index = 6. nums[6] becomes -3. nums = [4, -3, -2, -7, 8, 2, -3, 1]
  5. Iteration 5: num = 8. Index = 7. nums[7] becomes -1. nums = [4, -3, -2, -7, 8, 2, -3, -1]
  6. Iteration 6: num = 2. Index = 1. nums[1] is already negative.
  7. Iteration 7: num = 3. Index = 2. nums[2] is already negative.
  8. Iteration 8: num = 1. Index = 0. nums[0] becomes -4. nums = [-4, -3, -2, -7, 8, 2, -3, -1]

Now we iterate and find positive numbers: nums[4] (8) is positive and nums[5] (2) is positive. That's incorrect.

Corrected Explanation and Iteration:

Let's correct the process, only marking the presence with a change in sign.

  1. Iteration 1: num = 4. nums[4-1] = nums[3] becomes negative, (abs(nums[3]) = 7) becomes -7. nums = [4,3,2,-7,8,2,3,1]
  2. Iteration 2: num = 3. nums[3-1] = nums[2] becomes -2. nums = [4,3,-2,-7,8,2,3,1]
  3. Iteration 3: num = 2. nums[2-1] = nums[1] becomes -3. nums = [4,-3,-2,-7,8,2,3,1]
  4. Iteration 4: num = 7. nums[7-1] = nums[6] becomes -3. nums = [4,-3,-2,-7,8,2,-3,1]
  5. Iteration 5: num = 8. nums[8-1] = nums[7] becomes -1. nums = [4,-3,-2,-7,8,2,-3,-1]
  6. Iteration 6 & 7: 2 and 3 are already marked.
  7. Iteration 8: num = 1. nums[1-1] = nums[0] becomes -4. nums = [-4,-3,-2,-7,8,2,-3,-1]

Now, we scan nums for positive numbers: 5 and 6 are missing (indexes 4 and 5 respectively)

Code

#include <vector>

std::vector<int> findDisappearedNumbers(std::vector<int>& nums) {
    std::vector<int> result;
    int n = nums.size();

    // Mark the presence of each number by negating the element at the corresponding index
    for (int num : nums) {
        int index = std::abs(num) - 1; //Handle duplicates
        if (nums[index] > 0) {
            nums[index] *= -1;
        }
    }

    // Find the missing numbers
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 0) {
            result.push_back(i + 1);
        }
    }

    return result;
}

Complexity

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array twice.
  • Space Complexity: O(1). We modify the input array in-place. The extra space used by result is proportional to the number of missing elements, which is at most n. However, this is considered constant space relative to the input size.