First Missing Positive Leetcode Problem 41 [Python Solution]

In this blog post, we’re going to tackle the First Missing Positive problem, which is categorized as a hard problem on LeetCode.

The problem statement is as follows:

Problem Overview

Given an unsorted integer array nums, our goal is to return the smallest missing positive integer.

The catch is that we must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Here’s an example to help illustrate the problem:

Example 1:

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

Example 2:

Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: The number 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 <= 105
-231 <= nums[i] <= 231 – 1

Now, let’s dive into the problem and discuss the solution.

Problem Overview

The problem is essentially asking us to find the smallest missing positive integer in an unsorted array, and it has some specific constraints.

We need to address the following key points:

We are given an unsorted integer array.
We need to find the smallest missing positive integer.
Our algorithm must run in O(n) time.
We must use O(1) auxiliary space.

To understand the problem better, let’s explore a few examples.

Example 1:

Input: nums = [1, 2, 0]
Output: 3

In this case, the array contains values 1, 2, and 0. The smallest missing positive integer is 3 because 1 and 2 are present in the array.

Example 2:

Input: nums = [3, 4, -1, 1]
Output: 2

Here, 1 is present in the array, but 2 is missing.

Therefore, the smallest missing positive integer is 2.

Example 3:

Input: nums = [7, 8, 9, 11, 12]
Output: 1

In this example, the smallest positive integer, 1, is missing in the array.

Thus, our answer is 1. Now that we understand the problem, let’s explore how to solve it efficiently while satisfying the given constraints.

Understanding Constraints

Before we dive into the solution, it’s important to understand the constraints provided in the problem statement:

Time Complexity (O(n)): We need to come up with a solution that operates in linear time.

This means that our algorithm should be able to handle large input arrays efficiently.

Space Complexity (O(1)): We’re restricted to using constant auxiliary space.

This implies that we can’t create additional data structures with a space complexity that depends on the size of the input array.

To meet these constraints, we must devise a clever algorithm.

First Missing Positive LeetCode Problem Solution

We’ll discuss two efficient approaches to solving the First Missing Positive problem.

The first approach will be the main focus, as it optimally meets the time and space complexity requirements.

The second approach will serve as an alternative, providing you with different perspectives.

1. Bruteforce Approach

Let’s start with a straightforward, bruteforce approach to solving this problem.

Although this approach doesn’t satisfy the O(1) space constraint, it helps us understand the problem better and sets the stage for the more efficient solution.

The bruteforce approach involves creating a hash set to store the positive integers from the input array.

We iterate through the array to populate this hash set, recording all positive values.

Then, we iterate through a range from 1 to the length of the input array, checking if each number exists in the hash set.

The first number that doesn’t exist in the hash set is the smallest missing positive integer.

Here’s a Python implementation of this approach:

def firstMissingPositive(nums):
    # Create a set to store positive integers
    num_set = set()

    # Populate the set with positive values from the array
    for num in nums:
        if num > 0:
            num_set.add(num)

    # Iterate through the range [1, len(nums) + 1] to find the missing positive
    for i in range(1, len(nums) + 2):
        if i not in num_set:
            return i

While this bruteforce approach works, it doesn’t meet the O(1) space complexity requirement.

We are using additional space to store positive integers.

To satisfy the space constraint, we need to devise a more efficient algorithm.

2. An Efficient Approach with Reasoning

To achieve an O(1) space complexity, we’ll adopt a different approach that involves modifying the input array itself.

This approach cleverly utilizes the array as both a data structure and a marker for positive integers.

Let’s break it down step by step.

Step 1: Eliminating Negative Values

The first step is to eliminate negative values and zeros from the array.

Negative values are irrelevant to us since they don’t represent positive integers.

Zeros don’t help us find the smallest missing positive integer either.

We can achieve this by changing all negative values to zeros.

for i in range(len(nums)):
    if nums[i] < 0:
        nums[i] = 0

Now, the input array nums only contains non-negative integers, but it may still have zeros.

Step 2: Marking Positive Integers

In this step, we’ll use the input array to mark positive integers.

We’ll do this by changing specific values to negative.

The key insight here is that we can map each positive integer to its corresponding index in the array.

Consider the example nums = [3, 4, 1, 1].

Here, the value 3 indicates that 1 exists, the value 4 indicates that 2 exists, and the first 1 has already been accounted for.

Therefore, we will change nums[0] to -1, nums[1] to -1, and nums[2] to -1 to mark the existence of 1 and 2.

Here’s the Python code to mark positive integers:

for num in nums:
    # Take the absolute value to get the index
    index = abs(num)

    # Ignore out-of-bounds values (greater than the array length)
    if index <= len(nums):
        # Mark the existence of a positive integer by negating the value
        nums[index - 1] = -abs(nums[index - 1])

Step 3: Finding the Smallest Missing Positive

Now that we’ve marked positive integers, we can iterate through the array to find the smallest missing positive integer.

The first positive value that remains positive is

our answer.

Its index in the array indicates the missing positive integer.

Here’s the Python code for this step:

for i in range(len(nums)):
    if nums[i] > 0:
        return i + 1  # Missing positive integer found


return len(nums) + 1

Now, let’s put all these steps together to solve the problem:

View on GitHub ➹

def firstMissingPositive(self, nums: List[int]) -> int:
        # Step 1: Eliminate negative values and values greater than the array length
        for i in range(len(nums)):
            if nums[i] &lt;= 0 or nums[i] > len(nums):
                nums[i] = len(nums) + 1

        # Step 2: Mark positive integers by changing the sign
        for num in nums:
            index = abs(num)
            if 1 &lt;= index &lt;= len(nums):
                if nums[index - 1] > 0:
                    nums[index - 1] *= -1

        # Step 3: Find the smallest missing positive integer
        for i in range(len(nums)):
            if nums[i] > 0:
                return i + 1

        # If all positive integers are present, return the next positive integer
        return len(nums) + 1

This solution satisfies the problem’s time complexity requirement (O(n)) and, more importantly, the space complexity requirement (O(1)).

Complexity Analysis

Let’s analyze the time and space complexity of our efficient solution.

Time Complexity: O(n)

The first loop (Step 1) to eliminate negative values iterates through the entire array, taking O(n) time.
The second loop (Step 2) to mark positive integers also iterates through the entire array, taking O(n) time.
The third loop (Step 3) to find the smallest missing positive integer iterates through the array once more, taking O(n) time.

Overall, the time complexity of our solution is O(n).

Space Complexity: O(1)

Our solution uses constant auxiliary space.

We modify the input array in place without any additional data structures, satisfying the O(1) space complexity constraint.

Final Thoughts

The First Missing Positive problem challenges us to find the smallest missing positive integer from an unsorted array while meeting specific time and space complexity constraints.

We’ve presented an efficient solution that cleverly modifies the input array to achieve O(1) space complexity.

This problem demonstrates how creative problem-solving and careful analysis of constraints can lead to optimal solutions.

By understanding the problem thoroughly and making smart use of available resources, you can tackle even the most challenging programming problems effectively.