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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment