First Missing Positive - Java Solution

1. Introduction

This blog post addresses the "First Missing Positive" problem, a classic in array manipulation and problem-solving with constraints on time and space complexity. The challenge is to find the smallest missing positive integer in an unsorted array with an emphasis on achieving O(n) time complexity and using only O(1) auxiliary space.

Problem

Given an unsorted integer array nums, the objective is to find the smallest missing positive integer. The solution must be efficient in terms of both time (O(n)) and space (O(1)).

Examples:

- Input: nums = [1,2,0]

Output: 3

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

Output: 2

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

Output: 1

2. Solution Steps

1. Iterate over the array and replace all negative numbers and zeros with a number larger than the array length (e.g., nums.length + 1).

2. For each number nums[i], mark the number at index |nums[i]| - 1 as negative, if it's positive.

3. Iterate through the array. The first index that contains a positive number indicates the first missing positive.

4. If all numbers are negative, the first missing positive is nums.length + 1.

3. Code Program

public class FirstMissingPositive {
    public static void main(String[] args) {
        int[] nums = {3, 4, -1, 1};
        System.out.println(firstMissingPositive(nums)); // Test the function
    }

    // Function to find the first missing positive integer
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Replace non-positive numbers with a number larger than array length
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // Use index as a hash to record the frequency of numbers
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // Find the first cell which isn't negative (i.e., the smallest missing positive)
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

Output:

2

Explanation:

1. firstMissingPositive: This function computes the first missing positive integer in nums.

2. First, it replaces non-positive numbers and numbers greater than the array length with a number larger than the array length.

3. Then, it marks numbers at certain indices as negative to record the presence of numbers in the array.

4. The function iterates through nums, looking for the first positive number, which indicates the missing positive integer.

5. If no such positive number is found, the smallest missing positive is nums.length + 1.

6. The solution efficiently uses the indices of the array as a hash map to track the presence of numbers, thus adhering to the O(n) time complexity and O(1) space complexity constraints.