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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All Numbers Disappeared in an Array

Number: 448

Difficulty: Easy

Paid? No

Companies: Amazon, Google, Tinkoff, Meta, Oracle

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, so each value can be mapped to an index in the array.
  • In-place modification can be achieved by marking the values at these mapped indices to indicate presence.
  • By iterating over the array after marking, the indices that were not marked (i.e., still positive) correspond to the missing numbers.
  • This solution avoids using extra space beyond the output array.

Space and Time Complexity

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

Solution

We iterate through the array and for each number, we determine its corresponding index (by taking the absolute value of the number and subtracting one). We then mark the number at that index as negative to indicate that the number (index + 1) exists in the array. Finally, we iterate through the array once more and collect all indices that still hold positive values; these indices correspond to numbers that did not appear in the original array.

Code Solutions

# Function to find all disappeared numbers in an array
def findDisappearedNumbers(nums):
    # Iterate over each number in the list
    for i in range(len(nums)):
        # Get the index corresponding to the current number (adjusting for 0-indexed array)
        index = abs(nums[i]) - 1
        # Mark the number at this index as negative if it is not already marked
        if nums[index] > 0:
            nums[index] = -nums[index]
    
    # Initialize the result list
    result = []
    # Iterate over the array to collect indices of numbers that did not appear
    for i, num in enumerate(nums):
        # If the number is positive, then index + 1 is missing in the original array
        if num > 0:
            result.append(i + 1)
    
    # Return the list of missing numbers
    return result

# Example usage:
# print(findDisappearedNumbers([4,3,2,7,8,2,3,1]))  # Output: [5,6]
← Back to All Questions