LeetCode Hard – First Missing Positive

Given an unsorted integer array nums, return the smallest missing positive integer.

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

Java Solution

To achieve O(n) time complexity and O(1) space complexity, you can use a variation of the cyclic sort algorithm. Here’s a Java solution for the problem:

public class FirstMissingPositive {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Perform cyclic sort to place each number in its correct position
        for (int i = 0; i < n; i++) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }

        // Find the first missing positive integer
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        FirstMissingPositive solution = new FirstMissingPositive();

        // Example 1
        int[] nums1 = {1, 2, 0};
        System.out.println("Example 1 Output: " + solution.firstMissingPositive(nums1));

        // Example 2
        int[] nums2 = {3, 4, -1, 1};
        System.out.println("Example 2 Output: " + solution.firstMissingPositive(nums2));

        // Example 3
        int[] nums3 = {7, 8, 9, 11, 12};
        System.out.println("Example 3 Output: " + solution.firstMissingPositive(nums3));
    }
}

This Java program defines a FirstMissingPositive class with the firstMissingPositive method. The cyclic sort is performed in-place, and then the first missing positive integer is found by iterating through the array. The main method demonstrates how to use the program with the provided examples.

Python Solution

Here’s the equivalent Python solution for finding the smallest missing positive integer using the cyclic sort algorithm:

class FirstMissingPositive:
    def firstMissingPositive(self, nums):
        n = len(nums)

        # Perform cyclic sort to place each number in its correct position
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

        # Find the first missing positive integer
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

# Example usage:
solution = FirstMissingPositive()

# Example 1
nums1 = [1, 2, 0]
print("Example 1 Output:", solution.firstMissingPositive(nums1))

# Example 2
nums2 = [3, 4, -1, 1]
print("Example 2 Output:", solution.firstMissingPositive(nums2))

# Example 3
nums3 = [7, 8, 9, 11, 12]
print("Example 3 Output:", solution.firstMissingPositive(nums3))

This Python code mirrors the Java solution. The FirstMissingPositive class has the firstMissingPositive method. The cyclic sort is performed in-place, and then the first missing positive integer is found by iterating through the array. The example usage section demonstrates how to use the program with the provided examples.