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

1. Utilize the array as a hash table: We can cleverly use the input array itself as a hash table. Since the numbers are in the range [1, n], we can use the value of each number to index into the array. We'll use the index (minus 1 to account for 0-based indexing) to mark that the number has been seen. We do this by negating the value at that index.

2. Iterate and mark: Iterate through the input array. For each number num, find the index index = abs(num) - 1. If the number at that index is positive, negate it. The abs() function handles the case where the number has already been negated in a previous iteration.

3. Identify missing numbers: After the first iteration, iterate through the array again. Any index with a positive value indicates that the number corresponding to that index (index + 1) is missing.

Explanation

The core idea is to use the array's indices to represent the presence or absence of numbers. By negating the value at the index corresponding to each number in the input, we effectively mark its presence. Numbers that remain positive after this process indicate that they were not present in the original array.

Let's trace Example 1:

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

1. Iteration 1:

   • num = 4: index = 3. nums[3] is 7, so nums[3] becomes -7.
   • num = 3: index = 2. nums[2] is 2, so nums[2] becomes -2.
   • num = 2: index = 1. nums[1] is 3, so nums[1] becomes -3.
   • num = 7: index = 6. nums[6] is 3, so nums[6] becomes -3.
   • num = 8: index = 7. nums[7] is 1, so nums[7] becomes -1.
   • num = 2: index = 1. nums[1] is -3, so it remains -3.
   • num = 3: index = 2. nums[2] is -2, so it remains -2.
   • num = 1: index = 0. nums[0] is 4, so nums[0] becomes -4.
   • Now nums is [-4,-3,-2,-7,8,-3,-3,-1]

2. Iteration 2:

   • We iterate through nums. Indices 4 and 5 have positive values. These correspond to the numbers 5 and 6 (index + 1).

Therefore, the missing numbers are 5 and 6.

Code

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int n = nums.length;

        // Mark the presence of each number by negating the value at its corresponding index.
        for (int num : nums) {
            int index = Math.abs(num) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }

        // Find the missing numbers.
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result.add(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 use constant extra space, excluding the space for the output list. The solution modifies the input array in-place.