[LeetCode] 41. First Missing Pos

</br>

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

</br>

Solution

The solution can look like this, whenever the nums[i] != i+1, we swap the number with nums[nums[i]-1] to make sure that every number in the array is in the correct order.

Once the array is sorted, we can check whether the nums[i] == i+1, and the first place that does not satisfy this requirement should be the output value.
</br>
However, what if the value of certain numbers in the array is way too big, then the array may not have enough space to store all the value. For example,

nums[] = {2,3,5,999998};

We can solve this problem by ignoring numbers that is bigger than the size of the array.

But another problem also rises. How can we make sure that the numbers we ignored have no influence on the output?

Well, as the only scenario that this large number may influence the output is that all the numbers before this large number must be present, for example

nums[] = {2,3,4,5,...,999997,999998};

and in this case, the array itself would be equally large, and have no problem containing all numbers.
</br>
The code is shown as below.
Java

public class Solution {
    public int firstMissingPositive(int[] nums) {
        
        int i=0;
        
        while(i<nums.length){
            
            if(nums[i] <= 0 || nums[i] > nums.length || nums[i] == i+1){
                i++;
                continue;
            }
            
            if(nums[nums[i]-1] != nums[i]) 
                swap(nums, i, nums[i]-1);
            else i++;
        }
        
        i=0;
        while(i<nums.length){
            if(nums[i] != i+1)
                return i+1;
            i++;
        }
        return i+1;
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

</br>