First Missing Positive problem solution (Leetcode)

First Missing Positive problem solution: 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 constant extra 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.

First Missing Positive problem solution (Leetcode)

Problem solution in Python

def firstMissingPositive(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    nums.sort()
    if 1 not in nums:
        return 1
    a = nums.index(1)
    for i in range(a+1, len(nums)):
        if nums[i] - nums[i-1] > 1:
            return nums[i-1] + 1
        if i == len(nums)-1:
            return nums[i] + 1
    return 2

Problem solution in Java

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        int first = 1;
        
        for (int num : nums) {
            if (num > 0) {
                set.add(num);
            }
            
            if (num == first) {
                first++;
                
                while (set.contains(first)) {
                    first++;
                }
            }
        }
        
        return first;
    }
}

Problem solution in C++

int firstMissingPositive(vector<int> a) {
    
    int i,n=a.size();
    for(i=0;i<n;i++)
        if(a[i]<=0 || a[i]>n)
            a[i] = INT_MAX;

    a.push_back(INT_MAX);
    for(i=0;i<n;i++)
    {
        if(abs(a[i])==INT_MAX) continue;
        
        if(a[abs(a[i])]>0)
            a[abs(a[i])] *= -1;
    }
    for(i=1;i<=n;i++)
        if(a[i]>0)
            break;
    
    return i;
}

Problem solution in C.

int firstMissingPositive(int* nums, int numsSize){
    int i = 0;
    
    while (i < numsSize)
    {
        int n = nums[i];
        
        /* Swap nums[i] to nums[nums[i] - 1] if possible */
        if (0 < n && n < (numsSize + 1) && (n - 1) != i && nums[n - 1] != n)
        {
            nums[i] = nums[n - 1];
            nums[n - 1] = n;
        }
        else
        {
            i++;
        }
    }
    
    for (i = 1; i < numsSize + 1; i++)
    {
        if (nums[i - 1] != i)
            break;
    }
    
    return i;
}