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 leverage the fact that the numbers are in the range [1, n]. We'll use the array itself to mark the presence of numbers. We'll use the index as the key and the sign of the value as the indicator.

2. Mark present numbers: Iterate through the array. For each number num, find its corresponding index (num - 1). If the value at that index is positive, negate it. This marks the number as present.

3. Identify missing numbers: After the first pass, iterate through the array again. Any index i where the value at nums[i] is positive indicates that the number i + 1 is missing.

4. Collect missing numbers: Create a list to store the missing numbers. Add i + 1 to this list for every positive value encountered.

Explanation

The core idea is to use the array's indices to represent the numbers from 1 to n. By negating the value at an index when we encounter the corresponding number, we effectively mark its presence. Any index with a positive value after the marking process indicates a missing number. This avoids the need for an extra hash table or set, improving space efficiency.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        int n = nums.Length;
        
        // Mark present numbers by negating values at corresponding indices
        for (int i = 0; i < n; i++) {
            int index = Math.Abs(nums[i]) - 1; // Adjust index for 1-based numbering
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }

        // Collect missing numbers
        List<int> missingNumbers = new List<int>();
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We perform two linear scans of the array.
• Space Complexity: O(1). We use a constant amount of extra space (excluding the output list, which is considered part of the output). The space used by the output list is proportional to the number of missing elements, which is at most n, but this is not considered auxiliary space.