First Missing Positive

• Sort the input array nums in non-decreasing order.
• Initialize a variable, expectedPositive, to 1.
• Iterate through the sorted array. For each number num:
  • If num is positive:
    • If num is equal to expectedPositive, we've found the number we were looking for, so we increment expectedPositive.
    • If num is greater than expectedPositive, it means expectedPositive is missing. Return expectedPositive.
    • If num is less than expectedPositive, it's a duplicate of a number we've already processed, so we do nothing.
• If the loop completes, it means all integers from 1 up to the last found positive were present. The answer is the final value of expectedPositive.

The algorithm begins by sorting the input array nums. Once sorted, we can perform a single linear scan to find the first gap in the sequence of positive integers starting from 1. We use a variable, say expectedPositive, initialized to 1. As we iterate through the sorted array, we compare each positive number with expectedPositive. If the current number matches expectedPositive, we increment expectedPositive to look for the next integer in the sequence. If we encounter a number that is greater than expectedPositive, we have found our gap, and expectedPositive is the smallest missing positive. We must also handle duplicates and non-positive numbers by skipping them appropriately. If we traverse the entire array, the answer is the final value of expectedPositive.

For example, if nums = [3, 4, -1, 1], sorting gives [-1, 1, 3, 4]. We expect 1, we find it, so we now expect 2. The next positive number is 3, which is greater than 2. Thus, 2 is the answer.

1import java.util.Arrays;2 3class Solution {4    public int firstMissingPositive(int[] nums) {5        Arrays.sort(nums);6        int expectedPositive = 1;7        for (int num : nums) {8            if (num > 0) {9                if (num == expectedPositive) {10                    expectedPositive++;11                } else if (num > expectedPositive) {12                    return expectedPositive;13                }14                // If num < expectedPositive, it's a duplicate or a smaller number15                // that has already been accounted for. We just ignore it.16            }17        }18        return expectedPositive;19    }20}

• Create a HashSet to store positive integers.
• Iterate through the input array nums. For each number, if it's positive, add it to the hash set.
• Let n be the length of the array.
• Iterate from i = 1 up to n + 1.
• In each iteration, check if i is present in the hash set.
• The first integer i that is not found in the set is the smallest missing positive. Return i.

To achieve a linear time solution, we can use extra space in the form of a hash set. The algorithm first populates a HashSet with all the positive integers from the nums array. This step takes O(n) time as we iterate through the array once, and hash set insertion is, on average, an O(1) operation.

After building the set, we need to find the first missing positive. We know the answer must lie in the range [1, n+1], where n is the number of elements in the array. So, we simply loop from i = 1 to n + 1 and use the hash set to check for the presence of each i. The first i that is not in the set is our result. This second loop also runs in O(n) time.

For instance, with nums = [3, 4, -1, 1], the set becomes {1, 3, 4}. We then check for 1 (present), then 2 (not present), so we return 2.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int firstMissingPositive(int[] nums) {6        Set<Integer> set = new HashSet<>();7        for (int num : nums) {8            if (num > 0) {9                set.add(num);10            }11        }12        13        int n = nums.length;14        for (int i = 1; i <= n + 1; i++) {15            if (!set.contains(i)) {16                return i;17            }18        }19        20        return -1; // Should not be reached21    }22}

• Phase 1: Rearrangement
  • Iterate through the array with an index i from 0 to n-1.
  • For each element nums[i], as long as it's a valid number (1 <= nums[i] <= n) and it's not in its correct place (nums[i] != nums[nums[i] - 1]), swap it with the element at its correct index (nums[i] - 1).
  • This process, often called Cyclic Sort, places each number x at index x-1 if possible.
• Phase 2: Find Missing
  • Iterate through the rearranged array from i = 0 to n-1.
  • The first index i where nums[i] != i + 1 indicates that i + 1 is the smallest missing positive. Return i + 1.
• If the second loop completes without returning, it means all numbers from 1 to n are present. The answer is n + 1.

This approach meets both time and space constraints by modifying the array in-place. The core idea is that the first missing positive must be in the range [1, n+1]. We can therefore use the array's indices 0 to n-1 to signify the presence of numbers 1 to n.

The algorithm works in two phases. In the first phase, we iterate through the array and place each number in its correct position. For a number x, its correct position is index x-1. So, for each nums[i], if it's a number between 1 and n and it's not already at nums[nums[i]-1], we swap it. We repeat this for the element at index i until it holds a number that doesn't belong in the [1, n] range or is already in its correct spot. Despite the nested loop appearance, the total number of swaps is at most n, making this phase O(n).

In the second phase, we iterate through the modified array. The first index i where nums[i] is not equal to i+1 reveals that i+1 is the first missing positive. If we iterate through the whole array and find no such mismatch, it means all numbers from 1 to n are present, and the answer must be n+1.

1class Solution {2    public int firstMissingPositive(int[] nums) {3        int n = nums.length;4 5        // Phase 1: Place each number in its correct spot6        int i = 0;7        while (i < n) {8            int correctIndex = nums[i] - 1;9            if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {10                // Swap nums[i] with the element at its correct index11                int temp = nums[i];12                nums[i] = nums[correctIndex];13                nums[correctIndex] = temp;14            } else {15                i++;16            }17        }18 19        // Phase 2: Find the first missing positive20        for (i = 0; i < n; i++) {21            if (nums[i] != i + 1) {22                return i + 1;23            }24        }25 26        // If all numbers from 1 to n are present27        return n + 1;28    }29}