Find All Numbers Disappeared in an Array

Problem Statement

In this problem, you are provided with an array nums containing n integers. Each integer in the array is guaranteed to be within the range from 1 to n, where n is the length of the array. The task is to identify and return all the integers within this range [1, n] that are not present in the array nums. These missing numbers need to be collected and returned in an array format.

Examples

Example 1

Input:

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

Output:

[5,6]

Example 2

Input:

nums = [1,1]

Output:

[2]

Constraints

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

Approach and Intuition

The goal is to find the numbers missing from the consecutive range [1, n] in the given array nums. Here's a breakdown of the methodology:

1. Use of Data Structure:

   • A simple Boolean array could be utilized to track which numbers are present in the array. The index can represent each number from 1 to n, and the truth value at each index can reflect the presence or absence of that number in nums.

2. Scan Through nums:

   • Iterate through each number in the nums array. For each number, mark its corresponding position (number as index) in the Boolean array as True or any other marker indicating its presence.

3. Identify Missing Numbers:

   • After marking the presence of numbers from nums, iterate through the Boolean array from 1 to n. Collect indices where the value is still False (or unmarked). These indices represent the numbers that are missing from nums.

4. Edge Cases:

   • If nums includes every number from 1 to n, the resulting list of missing numbers would be empty.
   • For smaller arrays or arrays with repeated numbers (e.g., [1,1]), this method effectively captures the missing numbers without needing multiple passes or additional space for counting.

This approach is space-efficient because it leverages information about the problem constraints such as the specific range of numbers and their count's relationship to the array's length (i.e., n equals the length of nums). This positions the solution to operate efficiently even as n reaches larger values up to the upper constraint limit.

Solutions

class Solution {
    public List<Integer> getMissingNumbers(int[] arr) {
        for (int index = 0; index < arr.length; index++) {
            int targetIndex = Math.abs(arr[index]) - 1;
            if (arr[targetIndex] > 0) {
                arr[targetIndex] = -arr[targetIndex];
            }
        }

        List<Integer> missingNumbers = new ArrayList<Integer>();
        for (int k = 1; k <= arr.length; k++) {
            if (arr[k - 1] > 0) {
                missingNumbers.add(k);
            }
        }
        
        return missingNumbers;
    }
}