Find All Numbers Disappeared in an Array easy

Problem Statement

Given an array nums of integers in the range [1, n] where n is the length of the array, find all the numbers that are missing from the range [1, n].

Example 1:

Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6] Explanation: The range [1,8] is [1,2,3,4,5,6,7,8]. The missing numbers are 5 and 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 input array contains numbers within a specific range (1 to n). We'll use the array indices to represent the numbers. If a number x is present, we can mark its index x-1 in some way. For instance, we can negate the value at that index.

2. Iterate and mark: Traverse the input array. For each number num, if the value at index abs(num) - 1 is positive, negate it. The abs() function is used because we might have already negated a value in a prior step.

3. Identify missing numbers: Iterate through the array again. Any index i whose value is still positive indicates that the number i + 1 is missing.

Explanation:

The core idea is to use the array itself to track which numbers are present. By negating the value at the index corresponding to a number, we effectively mark its presence. Numbers that remain positive after this process were not present in the input. We use the absolute value to handle cases where a number has already been negated.

Code:

def findDisappearedNumbers(nums):
    """
    Finds all numbers that are missing from the range [1, n] in the input array.

    Args:
      nums: A list of integers.

    Returns:
      A list of integers representing the missing numbers.
    """

    n = len(nums)
    for num in nums:
        index = abs(num) - 1
        if nums[index] > 0:  #Only negate if not already negated
            nums[index] *= -1

    missing_numbers = []
    for i, num in enumerate(nums):
        if num > 0:
            missing_numbers.append(i + 1)

    return missing_numbers


# Example usage
nums1 = [4, 3, 2, 7, 8, 2, 3, 1]
print(findDisappearedNumbers(nums1))  # Output: [5, 6]

nums2 = [1, 1]
print(findDisappearedNumbers(nums2))  # Output: [2]

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 are modifying the input array in-place, so the extra space used is constant. We only use a small amount of extra space to store the result.