Jobs

Interviews

Discussions

Find All Numbers Disappeared in an Array

Easy

Find All Numbers Disappeared in an Array

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array contain duplicate numbers?
Is the input array guaranteed to be non-empty?
What should I return if the input array is null or empty?
Can I modify the input array in place?

Brute Force Solution

Approach

We are given a collection of numbers. Our goal is to find which numbers, within a specific range, are missing from that collection. The most straightforward way to do this is to check each number in the range individually to see if it's present in our collection.

Here's how the algorithm would work step-by-step:

Consider the complete list of numbers from 1 up to the size of the collection you were given.
Take the first number from this complete list.
See if that number exists anywhere within the collection you were given.
If it doesn't exist, mark it as missing.
Repeat steps 2-4 for every number in the complete list.
Once you've checked every number, present the list of all the numbers you marked as missing.

Code Implementation

def find_disappeared_numbers_brute_force(numbers):
    missing_numbers = []
    array_size = len(numbers)

    # Iterate through the expected range of numbers
    for expected_number in range(1, array_size + 1):
        is_present = False

        # Check if the current expected number exists in the input array
        for number in numbers:
            if number == expected_number:
                is_present = True
                break

        # Add to missing list if not found
        if not is_present:

            # Because this number is absent, add to the result
            missing_numbers.append(expected_number)

    return missing_numbers

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through a range of numbers from 1 to n (where n is the size of the input array). For each number in this range, it searches the entire input array to check for its presence. Therefore, for each of the n numbers in the range 1 to n, a linear search of O(n) is performed on the input array. Consequently, the overall time complexity is n * n, which simplifies to O(n²).

Space Complexity

O(N) – The described solution iterates from 1 to N (where N is the size of the input collection), checking if each number exists in the input. To store the missing numbers, a new list is implicitly used to 'mark them as missing'. This missing numbers list can potentially store up to N numbers in the worst-case scenario (when all numbers from 1 to N are missing from the original collection). Therefore, the algorithm uses auxiliary space proportional to the input size N, resulting in O(N) space complexity.

Optimal Solution

Approach

The best way to solve this problem is to cleverly use the existing list itself to keep track of which numbers are present. We can do this without needing extra space by changing the signs of numbers in the list.

Here's how the algorithm would work step-by-step:

Go through each number in the list.
For each number, find the corresponding spot in the list based on its value. Make the number at that spot negative (if it's not already negative). Think of it like marking that number as 'seen'.
Go through the list one more time.
If a number in the list is positive, it means the corresponding number was never 'seen' in the first step. This means that number is missing from the original list.
Create a new list of all the missing numbers you found.

Code Implementation

def find_disappeared_numbers(numbers):
    list_length = len(numbers)

    # Mark each number as seen by negating the value at its index.
    for number in numbers:
        index = abs(number) - 1

        if numbers[index] > 0:

            numbers[index] *= -1

    missing_numbers = []

    # If a value is positive, then that index + 1 is missing
    for index in range(list_length):

        if numbers[index] > 0:

            missing_numbers.append(index + 1)

    return missing_numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n twice. The first loop iterates through each number in the array to mark the presence of numbers by changing the sign of elements at specific indices. The second loop iterates through the array again to identify the indices that are still positive, indicating missing numbers. Since both loops iterate n times independently, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm modifies the input array in-place and creates only a new list to store the missing numbers. The size of this new list will be at most N, where N is the number of elements in the input array. However, the problem statement allows us to return the result as a list, which is inherent to the problem's output, and thus doesn't count towards auxiliary space. Therefore, the auxiliary space used is constant as it only uses a fixed number of variables for iteration regardless of the size of the input array.

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list as there are no numbers to check for disappearance.
Input array with only one element	Return a list containing all numbers from 1 to n that are not the single element in the input array.
Input array where all numbers from 1 to n are present	Return an empty list because no numbers are missing.
Input array contains duplicate numbers	The solution correctly identifies missing numbers even with duplicates because the marking or swapping mechanism will only be applied once per present number.
Input array contains numbers outside the range [1, n]	Ignore numbers outside the range as they do not affect the identification of missing numbers within the [1, n] range.
Large input array causing potential memory issues	The in-place modification approach minimizes memory usage, scaling better than approaches that use auxiliary data structures of size n.
Input array where n is close to the maximum integer value	The in-place modification should avoid integer overflow issues as we are only modifying existing values by using their indices.
Array contains extreme boundary values (1 and n)	The in-place marking should handle 1 and n correctly due to the index mapping from value - 1 to index.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array contain duplicate numbers?
Is the input array guaranteed to be non-empty?
What should I return if the input array is null or empty?
Can I modify the input array in place?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the complete list of numbers from 1 up to the size of the collection you were given.
Take the first number from this complete list.
See if that number exists anywhere within the collection you were given.
If it doesn't exist, mark it as missing.
Repeat steps 2-4 for every number in the complete list.
Once you've checked every number, present the list of all the numbers you marked as missing.

Code Implementation

def find_disappeared_numbers_brute_force(numbers):
    missing_numbers = []
    array_size = len(numbers)

    # Iterate through the expected range of numbers
    for expected_number in range(1, array_size + 1):
        is_present = False

        # Check if the current expected number exists in the input array
        for number in numbers:
            if number == expected_number:
                is_present = True
                break

        # Add to missing list if not found
        if not is_present:

            # Because this number is absent, add to the result
            missing_numbers.append(expected_number)

    return missing_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each number in the list.
For each number, find the corresponding spot in the list based on its value. Make the number at that spot negative (if it's not already negative). Think of it like marking that number as 'seen'.
Go through the list one more time.
If a number in the list is positive, it means the corresponding number was never 'seen' in the first step. This means that number is missing from the original list.
Create a new list of all the missing numbers you found.

Code Implementation

def find_disappeared_numbers(numbers):
    list_length = len(numbers)

    # Mark each number as seen by negating the value at its index.
    for number in numbers:
        index = abs(number) - 1

        if numbers[index] > 0:

            numbers[index] *= -1

    missing_numbers = []

    # If a value is positive, then that index + 1 is missing
    for index in range(list_length):

        if numbers[index] > 0:

            missing_numbers.append(index + 1)

    return missing_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list as there are no numbers to check for disappearance.
Input array with only one element	Return a list containing all numbers from 1 to n that are not the single element in the input array.
Input array where all numbers from 1 to n are present	Return an empty list because no numbers are missing.
Input array contains duplicate numbers	The solution correctly identifies missing numbers even with duplicates because the marking or swapping mechanism will only be applied once per present number.
Input array contains numbers outside the range [1, n]	Ignore numbers outside the range as they do not affect the identification of missing numbers within the [1, n] range.
Large input array causing potential memory issues	The in-place modification approach minimizes memory usage, scaling better than approaches that use auxiliary data structures of size n.
Input array where n is close to the maximum integer value	The in-place modification should avoid integer overflow issues as we are only modifying existing values by using their indices.
Array contains extreme boundary values (1 and n)	The in-place marking should handle 1 and n correctly due to the index mapping from value - 1 to index.