First Missing Positive in C


  • 0
    P

    ** 41. First Missing Positive **


    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.


    Approach: Efficient Solution

    ** Logic **

    If the input array is of size n, then missing positive number will lie either in [1,n]
    or it will be > n based on the elements present in the array.
    For Example, if an array is [1,2,3], then first missing positive number is 4 but if an array given is
    [100], first missing positive is 1. So, if every element is mapped to its index in the array then
    first unmapped index returns first missing positive, if all indices are mapped , then first missing number
    is the sizeof(array)+1.

    ** Proof **

    Let's have an array of integers of size n and organized as [1,2,3, ..., n-2, n-1], then every element is mapped to index of
    an array. 1 is mapped to 0, 2 is mapped to 1 , n is mapped to n-1, which means first unmapped index is n, which is our first missing positive.
    For another array which contains [100], 100 is mapped to 99, so, index 0 is unmapped and 1 is mapped to 0 which is our first missing positive.
    So, in an array, if index i is mapped, then i+1 element must be present in the array. Hence least index i returns first missing positive.

    C

    int firstMissingPositive(int* nums, int numsSize) {
    
        int i = 0;
    
        // Make sure that id is not present in nums
        int mappedValue = 0xdeadbeef;
    
        //
        // Base conditions, hardcoding logic:
        // For Array of size 0, first missing positive is 1
        // For Array of size 1 and the first number is negative 
        //    or greater than 1, return 1
        // For Array of size 1, if the first number is 1, return 2
        // 
        if(numsSize == 0) return 1;
        if(numsSize == 1 && (nums[0] > 1 || nums[0] < 1)) return 1;
        if(numsSize == 1 && nums[0] == 1) return 2;
    
        while(i < numsSize)
        {
            //
            // Ignore values which are:
            //      1. Out of array indexes as they will not be mapped in the array
            //      2. Negative numbers
            //      3. Already mapped values
            //
            if (nums[i] <= numsSize && nums[i] > 0 && nums[nums[i]-1] != mappedValue)
            {
                // Get the mapped index of the number nums[i]
                int t = nums[i]-1;
    
                // Move it to its index
                SWAP(nums[i], nums[t]);
    
                // map it to the index
                nums[t] = mappedValue; 
            }
           else
                i++;
        }
    
        // find first index which is not mapped
        for(int i = 0; i < numsSize; i++)
            if(nums[i] != id) return i+1;
    
        // if all indices are mapped, return sizeof(array)+1
        return numsSize+1;
    }
    

    Complexity Analysis

    • Time complexity : O(n).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.