Jobs

Interviews

Discussions

First Missing Positive

Hard

Netflix

16 views

Topics:

Arrays

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

First Missing Positive

Hard

Netflix

16 views

Topics:

Arrays

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

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:

Can the input array `nums` contain negative numbers, zeros, or duplicates?
What is the expected range of values within the `nums` array (e.g., are there any constraints on the magnitude of the numbers)?
If the input array `nums` is empty, what should I return?
If there is no missing positive integer (e.g., `nums` contains `[1, 2, 3]`), what value should I return?
Can I modify the input array `nums` in place, or do I need to preserve its original state?

Brute Force Solution

Approach

To find the smallest missing positive number, we'll simply check for each positive integer, starting from 1, to see if it's present in the input. We stop when we find the first positive integer that's not there.

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

Start with the number 1.
Check if 1 is in the given set of numbers.
If 1 is NOT in the set, then 1 is the answer, and you're done.
If 1 IS in the set, move to the next number, which is 2.
Check if 2 is in the given set of numbers.
If 2 is NOT in the set, then 2 is the answer, and you're done.
If 2 IS in the set, continue this process with the next positive integer, and so on.
Keep going until you find a positive integer that is not present in the original set of numbers. That number is your answer.

Code Implementation

def first_missing_positive_brute_force(numbers):
    smallestPositiveInteger = 1

    while True:
        # Keep looping and incrementing until we find the missing positive.
        if smallestPositiveInteger not in numbers:

            #If the smallest positive integer is NOT in the input, return it
            return smallestPositiveInteger

        # Increment to check the next positive integer.
        smallestPositiveInteger += 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through positive integers, starting from 1, until it finds one missing from the input. For each positive integer checked, it iterates through the input array of size n to see if the integer exists. In the worst case, where the first missing positive integer is larger than n, the algorithm performs approximately n checks of integers from 1 to n, each requiring a linear scan of the array. Therefore, the time complexity is proportional to n * n which simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a process of iteratively checking positive integers starting from 1. No auxiliary data structures like arrays, hash maps, or other collections are used to store information about the input array. The algorithm only needs to store the current positive integer being checked, which takes up constant space regardless of the input array's size, N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The core idea is to cleverly rearrange the input so the answer is sitting in a predictable spot. We leverage the input's structure to perform a more targeted search. This targeted rearrangement helps us avoid checking every single number in a separate search.

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

First, check if the number 1 is present. If not, 1 is the answer and we're done.
Replace negative numbers, zeros, and numbers larger than the size of the input with 1s. This ensures every spot holds a positive number that could potentially be the missing one.
Now, use the input as a lookup table. If a number, let's say 'k', is between 1 and the size of the input, change the sign of the k-th element. Be careful with duplicates; only change the sign once.
Go through the modified input. The index of the first positive number is the answer.
If the whole input is negative, the answer is one greater than the size of the input. All numbers from 1 to the size were present, so the next missing positive must be the next number.

Code Implementation

def first_missing_positive(numbers):
    array_length = len(numbers)

    if 1 not in numbers:
        return 1

    # Replace negatives, zeros, and nums > n with 1s
    # After this conversion, nums will contain only positive numbers.
    for i in range(array_length):
        if numbers[i] <= 0 or numbers[i] > array_length:
            numbers[i] = 1

    # Use index as a hash key and number sign as a presence detector.
    # For example, if nums[1] is negative, that means that the number `1`
    # is present in the array.
    # If nums[2] is positive, the number 2 is missing.
    for i in range(array_length):
        absolute_value = abs(numbers[i])
        if absolute_value <= array_length:
            numbers[absolute_value - 1] = - abs(numbers[absolute_value - 1])

    # Now the index of the first positive number
    # is equal to the first missing positive.
    for i in range(array_length):
        if numbers[i] > 0:
            return i + 1

    # If nums[i] > 0 is never triggered, that means
    # that the answer is array_length + 1.
    return array_length + 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm consists of a few linear passes through the input array nums of size n. The first pass checks for the presence of 1. The second pass replaces out-of-range numbers with 1. The third pass uses the array as a hash table, changing the sign of elements at specific indices. The final pass searches for the first positive number. Since each pass iterates through the array at most once, the time complexity is dominated by these linear operations, resulting in a total time complexity of O(n).

Space Complexity

O(1) – The algorithm operates in place, modifying the input array directly. It uses a constant number of variables for iteration and temporary storage, irrespective of the input size N, where N is the length of the input array. Therefore, the auxiliary space required remains constant, independent of the input size, and is considered O(1).

Edge Cases

Case	How to Handle
Empty array or null input	Return 1, since the smallest missing positive is 1 when no positives are present.
Array with only negative numbers or zeros	Return 1, as no positive numbers exist in the input.
Array containing only the number 1	Return 2, since 1 exists and 2 is the smallest missing positive.
Array containing `n` where `n` is the size of the array, but not containing 1.	The algorithm should correctly identify 1 as the missing number after placing all positives in their respective positions.
Array containing duplicates and a large range of numbers, including some positive numbers within the range [1, n]	The cyclic sort or in-place modification will handle duplicates correctly by skipping over them after one encounter and the relevant range allows finding smallest missing.
Array containing all positive numbers from 1 to n	Return n + 1 since all numbers from 1 to n are present.
Array containing extremely large positive and negative numbers	The algorithm will only operate on numbers within the range [1, n] and effectively ignore out-of-range numbers.
Array containing only Integer.MAX_VALUE or Integer.MIN_VALUE	The algorithm correctly ignores Integer.MAX_VALUE and Integer.MIN_VALUE since they are outside the [1,n] range

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:

Can the input array `nums` contain negative numbers, zeros, or duplicates?
What is the expected range of values within the `nums` array (e.g., are there any constraints on the magnitude of the numbers)?
If the input array `nums` is empty, what should I return?
If there is no missing positive integer (e.g., `nums` contains `[1, 2, 3]`), what value should I return?
Can I modify the input array `nums` in place, or do I need to preserve its original state?

Brute Force Solution

Approach

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

Start with the number 1.
Check if 1 is in the given set of numbers.
If 1 is NOT in the set, then 1 is the answer, and you're done.
If 1 IS in the set, move to the next number, which is 2.
Check if 2 is in the given set of numbers.
If 2 is NOT in the set, then 2 is the answer, and you're done.
If 2 IS in the set, continue this process with the next positive integer, and so on.
Keep going until you find a positive integer that is not present in the original set of numbers. That number is your answer.

Code Implementation

def first_missing_positive_brute_force(numbers):
    smallestPositiveInteger = 1

    while True:
        # Keep looping and incrementing until we find the missing positive.
        if smallestPositiveInteger not in numbers:

            #If the smallest positive integer is NOT in the input, return it
            return smallestPositiveInteger

        # Increment to check the next positive integer.
        smallestPositiveInteger += 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, check if the number 1 is present. If not, 1 is the answer and we're done.
Replace negative numbers, zeros, and numbers larger than the size of the input with 1s. This ensures every spot holds a positive number that could potentially be the missing one.
Now, use the input as a lookup table. If a number, let's say 'k', is between 1 and the size of the input, change the sign of the k-th element. Be careful with duplicates; only change the sign once.
Go through the modified input. The index of the first positive number is the answer.
If the whole input is negative, the answer is one greater than the size of the input. All numbers from 1 to the size were present, so the next missing positive must be the next number.

Code Implementation

def first_missing_positive(numbers):
    array_length = len(numbers)

    if 1 not in numbers:
        return 1

    # Replace negatives, zeros, and nums > n with 1s
    # After this conversion, nums will contain only positive numbers.
    for i in range(array_length):
        if numbers[i] <= 0 or numbers[i] > array_length:
            numbers[i] = 1

    # Use index as a hash key and number sign as a presence detector.
    # For example, if nums[1] is negative, that means that the number `1`
    # is present in the array.
    # If nums[2] is positive, the number 2 is missing.
    for i in range(array_length):
        absolute_value = abs(numbers[i])
        if absolute_value <= array_length:
            numbers[absolute_value - 1] = - abs(numbers[absolute_value - 1])

    # Now the index of the first positive number
    # is equal to the first missing positive.
    for i in range(array_length):
        if numbers[i] > 0:
            return i + 1

    # If nums[i] > 0 is never triggered, that means
    # that the answer is array_length + 1.
    return array_length + 1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty array or null input	Return 1, since the smallest missing positive is 1 when no positives are present.
Array with only negative numbers or zeros	Return 1, as no positive numbers exist in the input.
Array containing only the number 1	Return 2, since 1 exists and 2 is the smallest missing positive.
Array containing `n` where `n` is the size of the array, but not containing 1.	The algorithm should correctly identify 1 as the missing number after placing all positives in their respective positions.
Array containing duplicates and a large range of numbers, including some positive numbers within the range [1, n]	The cyclic sort or in-place modification will handle duplicates correctly by skipping over them after one encounter and the relevant range allows finding smallest missing.
Array containing all positive numbers from 1 to n	Return n + 1 since all numbers from 1 to n are present.
Array containing extremely large positive and negative numbers	The algorithm will only operate on numbers within the range [1, n] and effectively ignore out-of-range numbers.
Array containing only Integer.MAX_VALUE or Integer.MIN_VALUE	The algorithm correctly ignores Integer.MAX_VALUE and Integer.MIN_VALUE since they are outside the [1,n] range