First Missing Positive

Clarify the problem

The First Missing Positive problem requires finding the smallest positive integer that does not exist in a given array of integers. The array may contain both positive and negative numbers, and we need to find the first missing positive integer.

Analyze the problem

We need to find the first missing positive integer, which means we are only concerned with positive integers greater than zero. The array can contain duplicates, and the missing positive integer must be greater than the maximum positive integer in the array. The problem constraints state that we should not use any predefined functions or imports.

Design an algorithm

To solve this problem without using predefined functions, we can use the following algorithm:

  • Iterate through the array and ignore any negative numbers or zero values.
  • For each positive number encountered, mark its corresponding index in the array as negative.
  • Iterate through the array again, and the first positive index indicates the smallest missing positive integer.

Explain your approach 

The approach is to iterate through the array twice. In the first iteration, we mark the indices of positive numbers as negative. In the second iteration, we find the first positive index, which represents the smallest missing positive integer.

Write clean and readable code 

Let's implement the algorithm in Python:

def firstMissingPositive(nums):
    n = len(nums)

    # Step 1: Ignore non-positive numbers
    for i in range(n):
        if nums[i] <= 0:
            nums[i] = n + 1

    # Step 2: Mark indices as negative
    for i in range(n):
        num = abs(nums[i])
        if num <= n:
            nums[num - 1] = -abs(nums[num - 1])

    # Step 3: Find the first positive index
    for i in range(n):
        if nums[i] > 0:
            return i + 1

    # All positive numbers exist, return the next integer
    return n + 1

Test your code 

Let's test the code with some example test cases and explain the chosen test cases:

# Test case 1
nums = [1, 2, 0]
# The smallest missing positive integer is 3
print(firstMissingPositive(nums))  # Output: 3

# Test case 2
nums = [3, 4, -1, 1]
# The smallest missing positive integer is 2
print(firstMissingPositive(nums))  # Output: 2

# Test case 3
nums = [7, 8, 9, 11, 12]
# The smallest missing positive integer is 1
print(firstMissingPositive(nums))  # Output: 1

Optimize if necessary 

The given algorithm has a time complexity of O(n) because we iterate through the array three times, each time with a single loop. This is the most optimal solution for this problem, so there's no need for further optimization.

Handle error cases 

The algorithm assumes that the input is a valid array of integers. If an invalid input is provided, such as a non-array or an array with non-integer values, the behavior is undefined. You can add error handling code at the beginning of the firstMissingPositive function to handle such cases and return an appropriate error message or value.

Discuss complexity analysis 

The algorithm has a time complexity of O(n), where n is the size of the input array. This is because we iterate through the array three times, each time with a single loop. The space complexity is O(1) because we only use a constant amount of additional space to store the variables used during the computation.

 

Next Post Previous Post