Problem: First Missing Positive

Given an unsorted integer array nums, find the smallest positive integer that is not present in the array. The algorithm must run in O(n) time and use O(1) auxiliary space.

Solution: In-place Swap

This solution utilizes an in-place swapping technique to efficiently find the smallest missing positive integer. The core idea is to use the array's indices to represent the presence or absence of positive integers.

Algorithm:

1. Range Consideration: We only need to consider positive integers within the range [1, n+1], where n is the length of the array. Numbers outside this range are irrelevant to the problem.

2. In-place Swapping: Iterate through the array. For each number x:

   • If x is within the range [1, n] and is not in its correct position (i.e., nums[x-1] != x), swap x with the element at index x-1. This places x in its correct position.
   • If x is outside the range [1, n] or is already in its correct position, continue to the next element.

3. Find Missing: After the swapping phase, iterate through the array again. The first index i where nums[i] != i+1 indicates that i+1 is the smallest missing positive integer. If no such index is found, the smallest missing positive integer is n+1.

Time Complexity: O(n)

The algorithm consists of two passes through the array, each taking O(n) time. The swapping operations within the inner while loop do not change the overall time complexity because, in the worst-case scenario, each element is swapped at most once.

Space Complexity: O(1)

The algorithm operates directly on the input array and uses only a constant amount of extra space for variables like i and j. Therefore, the space complexity is constant.

Code Examples (Python, Java, C++, and more)

The provided code examples demonstrate the algorithm's implementation in multiple programming languages. Each example follows the same algorithmic steps:

Python:

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

Java:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        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 t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

C++:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

(Other languages like Go, TypeScript, Rust, C#, and PHP are also provided in the original response). All these examples share the same fundamental logic, adapting only to the syntactic differences of each language.