First Missing Positive hard

Problem Statement

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

You must implement an algorithm with O(n) time complexity and O(1) space complexity.

Example 1:

Input: nums = [1,2,0] Output: 3 Explanation: The numbers 1, 2, and 0 are present in nums, so the smallest missing positive integer is 3.

Example 2:

Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest missing positive integer is 1 because it is not in the array.

Steps and Explanation

The key to solving this problem efficiently lies in using the input array itself as a hash table. Since we're only interested in positive integers, we can use the array indices to represent the numbers.

1. Handle Negative and Out-of-Bound Numbers: First, we iterate through the array. Any number less than or equal to 0 or greater than n (where n is the length of the array) can be ignored because they cannot be the smallest missing positive integer. We replace these numbers with 1. This ensures we don't accidentally use invalid indices later.

2. Mark Present Numbers: Next, we iterate again. For each number num in the array, if it's within the valid range (1 to n), we use its absolute value as an index and mark the element at that index as negative. We use the absolute value to handle the cases where a number was already marked negative in the previous step. Essentially, we're marking the presence of the number num.

3. Find the Missing Positive: Finally, we iterate one last time. The first index i whose corresponding element nums[i] is positive indicates that i + 1 is the smallest missing positive integer. If all elements are negative, it means all numbers from 1 to n are present, so the smallest missing positive integer is n + 1.

Code (Java)

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

        // Handle negative and out-of-bound numbers
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = 1; // Mark as present (can be any positive value)
            }
        }

        // Mark present numbers using their absolute values as indices
        for (int i = 0; i < n; i++) {
            int index = Math.abs(nums[i]) - 1; // Adjust index to 0-based
            if (nums[index] > 0) {
                nums[index] = -nums[index]; // Mark as present using negative sign
            }
        }

        // Find the first positive number (missing positive)
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1; // i + 1 because index is 0-based
            }
        }

        // If all numbers from 1 to n are present, the smallest missing is n + 1
        return n + 1;
    }
}

Complexity

• Time Complexity: O(n). We iterate through the array a constant number of times (three times in this case).
• Space Complexity: O(1). We modify the input array in-place, using no additional data structures whose size depends on the input. Therefore, the space complexity is constant.