We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All Numbers Disappeared in an Array

Difficulty: Easy

Problem Description

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Key Insights

  • The input array contains integers from 1 to n, where n is the length of the array.
  • Some integers in this range may be missing from the array.
  • The task is to identify all integers in the range that are not present in the input array.
  • A solution that utilizes the input array without additional space can be achieved by leveraging index manipulation.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (excluding the output array)

Solution

The solution involves iterating through the input array and using the values to mark indices corresponding to the numbers found in the array. This is done by negating the value at the index equal to the current number minus one. After processing the array, the indices that remain positive indicate the missing numbers. The final results are collected and returned.

Code Solutions

def findDisappearedNumbers(nums):
    n = len(nums)
    # Mark the indices based on the values in the array
    for num in nums:
        index = abs(num) - 1
        nums[index] = -abs(nums[index])
    
    # Collect the missing numbers
    missing_numbers = []
    for i in range(n):
        if nums[i] > 0:
            missing_numbers.append(i + 1)
    
    return missing_numbers
← Back to All Questions