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