Jobs

Interviews

Discussions

Smallest Missing Non-negative Integer After Operations

Medium

Atlassian

1 view

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed integer array nums and an integer value.

In one operation, you can add or subtract value from any element of nums.

For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].

The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.

For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2.

Return the maximum MEX of nums after applying the mentioned operation any number of times.

Example:

nums = [1,-10,7,13,6,8], value = 5

What is the maximum MEX of nums?

Smallest Missing Non-negative Integer After Operations

Medium

Atlassian

1 view

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed integer array nums and an integer value.

In one operation, you can add or subtract value from any element of nums.

For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].

The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.

For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2.

Return the maximum MEX of nums after applying the mentioned operation any number of times.

Example:

nums = [1,-10,7,13,6,8], value = 5

What is the maximum MEX of nums?

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 are the constraints on the size of the `nums` array and the range of values within `nums` and `value`?
If after the operations, all non-negative integers up to a certain point are present in the modified array, what should be returned? Should I return the next integer?
Can I modify the original `nums` array in place, or do I need to create a copy?
Are there any constraints on the data types used? Specifically, is `value` always a non-negative integer?
If the input array is empty, what value should I return?

Brute Force Solution

Approach

The brute force way to find the smallest missing non-negative number after some operations involves systematically checking each non-negative number one by one. We repeatedly simulate the operations on the initial set of numbers and then see if the number we are checking is present. If a number is never present after any of the possible operation combinations, it's a potential answer.

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

Start with the number zero.
Imagine trying every possible combination of the given operations on the original set of numbers.
After performing one specific combination of operations, check if the number zero exists in the modified set of numbers.
If it doesn't exist, then zero is the smallest missing number; we're done!
If zero *does* exist after that particular combination, move on to the next possible combination of operations and check again.
If zero exists after *all* possible combinations of operations, then we know zero is not the missing number. Move on to the number one.
Repeat this whole process for the number one: try every possible combination of operations, and check if one exists in the modified set after each combination.
Continue this process, checking each number (two, three, four, and so on) in increasing order, until you find a number that *never* appears after *any* combination of operations. That number is the smallest missing non-negative integer.

Code Implementation

def find_smallest_missing_number_brute_force(initial_numbers, operations):
    missing_number_candidate = 0

    while True:
        # Assume the current number is missing until proven otherwise
        is_missing = True

        # Iterate through all possible combinations of operations
        for i in range(1 << len(operations)):
            modified_numbers = initial_numbers[:]
            operation_combination = []

            for operation_index in range(len(operations)):
                # Determine if the current operation should be applied
                if (i >> operation_index) & 1:
                    operation_combination.append(operations[operation_index])

            # Apply the selected operations to the numbers
            for operation in operation_combination:
                for index in range(len(modified_numbers)):
                    modified_numbers[index] = operation(modified_numbers[index])

            # Check if the candidate exists in the modified set.
            if missing_number_candidate in modified_numbers:
                # If it exists in any combination, it's not missing
                is_missing = False
                break

        # If the number remains missing after all combinations, return it.
        if is_missing:
            return missing_number_candidate

        missing_number_candidate += 1

Big(O) Analysis

Time Complexity

O(Infinity) – The algorithm iterates through non-negative integers (0, 1, 2, ...), attempting to find the smallest missing one. For each integer, it tries all possible combinations of operations on the initial set of numbers. Because the number of non-negative integers is infinite and the number of operation combinations can also be incredibly large (potentially exponential depending on the operations and input array size, n), the algorithm might never terminate if the missing integer is large or the operations are complex. Thus the time complexity is effectively infinite.

Space Complexity

O(N * 2^M) – The algorithm iterates through non-negative integers, and for each integer, it simulates every possible combination of the given M operations on the original set of N numbers. To simulate each combination of operations, a copy of the initial set of N numbers might be created and modified, using O(N) space. Since there are 2^M possible combinations of operations, storing the modified set for each combination in the worst case would require O(N * 2^M) space. Therefore, the overall auxiliary space complexity is O(N * 2^M), where N is the number of elements in the initial set, and M is the number of operations.

Optimal Solution

Approach

We want to find the smallest missing number after making changes to our numbers. The key idea is to ensure the first few non-negative integers (0, 1, 2, ...) are present in our set. We'll achieve this by systematically replacing larger, irrelevant numbers with these smaller, potentially missing ones.

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

Determine the size of the original set of numbers.
Go through the original numbers and if you find one which is greater than or equal to the size of the array, replace it with a zero. The numbers that are greater or equal to the array size don't affect the answer.
Create a new set (or reuse the original one) and try to fill it with numbers zero, one, two, and so on, until we reach the size of the set.
During this filling process, if we can swap out a number from the original set (that we've already determined doesn't matter) with the needed number, we do that swap. We are using the operation we are given in the question to convert a number to another number.
After this process, check which is the smallest number (zero, one, two, and so on) that's now missing from our set.
That missing number is our answer.

Code Implementation

def find_smallest_missing(numbers):
    array_size = len(numbers)

    # Replace numbers >= array_size with 0
    for index in range(array_size):
        if numbers[index] >= array_size:
            numbers[index] = 0

    # Use the input array to keep track of presence
    for index in range(array_size):
        correct_index = numbers[index]

        # Ensures that numbers are placed in the right index
        while numbers[index] != index and numbers[index] < array_size:
            correct_index = numbers[index]

            # Check for duplicates before swapping
            if numbers[index] == numbers[correct_index]:
                break

            numbers[index], numbers[correct_index] = numbers[correct_index], numbers[index]

    # The first index that does not match is the answer
    for index in range(array_size):
        if numbers[index] != index:
            return index

    return array_size

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n to replace numbers greater than or equal to n with zeros, which takes O(n) time. Then, the algorithm iterates up to n times to try and place the numbers 0, 1, 2, ..., n-1 into the array by potentially swapping numbers. Each swap operation is considered O(1). Finally, it iterates through the modified array one last time to find the smallest missing non-negative integer, taking another O(n) time. Thus the dominant operation is the initial replacement of elements and the subsequent placement of correct elements which scales linearly to the size of the array which gives a O(n) time complexity.

Space Complexity

O(1) – The provided algorithm primarily operates in-place. While it mentions creating a new set, it also suggests reusing the original, implying in-place modification. The only extra memory used is for a few integer variables, such as counters or temporary storage during swaps, the number of which does not depend on the input size, N (the size of the original set). Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Empty input array	Return 0 because 0 is the smallest non-negative integer and the array is empty, so it's missing.
Value is zero	When value is zero, the problem reduces to finding the smallest missing non-negative integer in the original array.
Array contains all numbers from 0 to n-1, where n is the array size	The answer should be n in this case, as it's the smallest missing non-negative integer.
Large array size with a small value and many duplicates	This can cause the same numbers to occur frequently within the allowed range after operations; use a set to efficiently track used numbers.
Large value where adding or subtracting from a small number results in values outside feasible integer range, or duplicates after applying operations	Ensure that operations are conducted in a way that prevents duplicates and stays within an acceptable integer range, possibly using modulus if applicable and using a set for existence checks.
Array contains only zeros	If value is zero, the answer is 1; otherwise, the answer is either zero or the smallest number reachable from zero (zero + value, zero - value, and zero itself).
Integer overflow when adding or subtracting 'value'	Use appropriate data types (e.g., long) to avoid integer overflow during the addition and subtraction operations, handling potential negative numbers caused by subtraction.
All numbers in nums are negative after applying the operations	The smallest missing non-negative integer will be 0 because all original numbers can be decremented below 0.

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 are the constraints on the size of the `nums` array and the range of values within `nums` and `value`?
If after the operations, all non-negative integers up to a certain point are present in the modified array, what should be returned? Should I return the next integer?
Can I modify the original `nums` array in place, or do I need to create a copy?
Are there any constraints on the data types used? Specifically, is `value` always a non-negative integer?
If the input array is empty, what value should I return?

Brute Force Solution

Approach

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

Start with the number zero.
Imagine trying every possible combination of the given operations on the original set of numbers.
After performing one specific combination of operations, check if the number zero exists in the modified set of numbers.
If it doesn't exist, then zero is the smallest missing number; we're done!
If zero *does* exist after that particular combination, move on to the next possible combination of operations and check again.
If zero exists after *all* possible combinations of operations, then we know zero is not the missing number. Move on to the number one.
Repeat this whole process for the number one: try every possible combination of operations, and check if one exists in the modified set after each combination.
Continue this process, checking each number (two, three, four, and so on) in increasing order, until you find a number that *never* appears after *any* combination of operations. That number is the smallest missing non-negative integer.

Code Implementation

def find_smallest_missing_number_brute_force(initial_numbers, operations):
    missing_number_candidate = 0

    while True:
        # Assume the current number is missing until proven otherwise
        is_missing = True

        # Iterate through all possible combinations of operations
        for i in range(1 << len(operations)):
            modified_numbers = initial_numbers[:]
            operation_combination = []

            for operation_index in range(len(operations)):
                # Determine if the current operation should be applied
                if (i >> operation_index) & 1:
                    operation_combination.append(operations[operation_index])

            # Apply the selected operations to the numbers
            for operation in operation_combination:
                for index in range(len(modified_numbers)):
                    modified_numbers[index] = operation(modified_numbers[index])

            # Check if the candidate exists in the modified set.
            if missing_number_candidate in modified_numbers:
                # If it exists in any combination, it's not missing
                is_missing = False
                break

        # If the number remains missing after all combinations, return it.
        if is_missing:
            return missing_number_candidate

        missing_number_candidate += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Determine the size of the original set of numbers.
Go through the original numbers and if you find one which is greater than or equal to the size of the array, replace it with a zero. The numbers that are greater or equal to the array size don't affect the answer.
Create a new set (or reuse the original one) and try to fill it with numbers zero, one, two, and so on, until we reach the size of the set.
During this filling process, if we can swap out a number from the original set (that we've already determined doesn't matter) with the needed number, we do that swap. We are using the operation we are given in the question to convert a number to another number.
After this process, check which is the smallest number (zero, one, two, and so on) that's now missing from our set.
That missing number is our answer.

Code Implementation

def find_smallest_missing(numbers):
    array_size = len(numbers)

    # Replace numbers >= array_size with 0
    for index in range(array_size):
        if numbers[index] >= array_size:
            numbers[index] = 0

    # Use the input array to keep track of presence
    for index in range(array_size):
        correct_index = numbers[index]

        # Ensures that numbers are placed in the right index
        while numbers[index] != index and numbers[index] < array_size:
            correct_index = numbers[index]

            # Check for duplicates before swapping
            if numbers[index] == numbers[correct_index]:
                break

            numbers[index], numbers[correct_index] = numbers[correct_index], numbers[index]

    # The first index that does not match is the answer
    for index in range(array_size):
        if numbers[index] != index:
            return index

    return array_size

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 because 0 is the smallest non-negative integer and the array is empty, so it's missing.
Value is zero	When value is zero, the problem reduces to finding the smallest missing non-negative integer in the original array.
Array contains all numbers from 0 to n-1, where n is the array size	The answer should be n in this case, as it's the smallest missing non-negative integer.
Large array size with a small value and many duplicates	This can cause the same numbers to occur frequently within the allowed range after operations; use a set to efficiently track used numbers.
Large value where adding or subtracting from a small number results in values outside feasible integer range, or duplicates after applying operations	Ensure that operations are conducted in a way that prevents duplicates and stays within an acceptable integer range, possibly using modulus if applicable and using a set for existence checks.
Array contains only zeros	If value is zero, the answer is 1; otherwise, the answer is either zero or the smallest number reachable from zero (zero + value, zero - value, and zero itself).
Integer overflow when adding or subtracting 'value'	Use appropriate data types (e.g., long) to avoid integer overflow during the addition and subtraction operations, handling potential negative numbers caused by subtraction.
All numbers in nums are negative after applying the operations	The smallest missing non-negative integer will be 0 because all original numbers can be decremented below 0.