First Missing Positive in C

• ** 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

//
// 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
//
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).

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