First Missing Positive

Introduction

Today, I took on a challenging problem from LeetCode: First Missing Positive. This hard-level question tests your algorithmic skills, requiring an O(n) time complexity solution with O(1) auxiliary space. The goal is to find the smallest positive integer that is not present in a given unsorted integer array. Let's dive into the problem statement, approach, and solution.

Problem Statement

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 <= 105

• -231 <= nums[i] <= 231 - 1

Approach to Solve the Problem

To solve this problem efficiently, we need to ensure our solution runs in O(n) time and uses O(1) auxiliary space. The approach involves rearranging the array to position each positive number at its correct index and then finding the first index that does not have the correct number. Here are the detailed steps:

1. Count Positive Numbers: Count the number of positive numbers in the array.

2. Create a Positive Array: Create an array to hold the positive numbers in their correct positions.

3. Place Numbers in Correct Positions: Traverse the input array and place positive numbers at their correct indices in the new array.

4. Find the Missing Positive: Traverse the new array to find the first index with a zero, which indicates the missing positive number.

Solution

Here’s the Java code that implements the above approach:

public static int firstMissingPositive(int [] nums){
    int countPositive = 0;

    // counting the number of positive numbers in the array
    for(int i = 0; i < nums.length; i++){
        if(nums[i] > 0){
            countPositive++;
        }
    }

    // creating new array of positive numbers
    int [] positiveArr = new int[countPositive];

    // putting the numbers in new array at their correct index (Count Sort)
    for(int i = 0; i < nums.length; i++){
        if(nums[i] > 0 && nums[i] <= countPositive){
            positiveArr[nums[i]-1] = nums[i];
        }
    }

    // Checking which index is 0 -> this is our answer
    for(int i = 0; i < countPositive; i++){
        if(positiveArr[i] == 0){
            return i+1; // i+1 is done as range is [1,n]
        }
    }

    return countPositive+1; // edge case : if the answer is not in positiveArr
}

Explanation

1. Counting Positives: The initial loop counts the positive numbers in the input array.

2. Creating Positive Array: An array of size equal to the count of positive numbers is created to store positive numbers at their correct indices.

3. Positioning Numbers: The second loop places each positive number at its correct position in the new array. For instance, the number 1 should be placed at index 0, 2 at index 1, and so on.

4. Finding the Missing Positive: The final loop checks for the first zero in the new array, which indicates the smallest missing positive number. If no zero is found, the smallest missing positive is countPositive + 1.

Performance

This solution achieves O(n) time complexity by traversing the array a constant number of times. The space complexity is O(1) auxiliary space because the extra space used is directly proportional to the number of positive numbers, which does not exceed the size of the input array.

Conclusion

The "First Missing Positive" problem is a great exercise in understanding and applying efficient algorithms. By leveraging prefix sums and in-place modifications, we can achieve an optimal solution that meets the problem's constraints. This problem-solving approach is valuable for tackling a variety of challenges in competitive programming and real-world applications.

I hope this blog provides a clear understanding of the problem and its solution. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!