Algo:

- Separate all positive numbers to the right and move forward to the problem.
- Find the missing positive the positive elements by :
- Mark arr[i] as visited by making arr[arr[i] - 1] negative.

... - Return the first index value at which is positive

- Mark arr[i] as visited by making arr[arr[i] - 1] negative.

/* swap two integers */

void swap(int *a, int *b)

{

int temp;

temp = *a;

*a = *b;

*b = temp;

}

/* puts all non-positive (0 and negative) numbers on left

side of arr[] and return count of such numbers */

int separateNP(int arr[], int size)

{

int j = 0, i;

for(i = 0; i < size; i++)

{

if (arr[i] <= 0)

{

swap(&arr[i], &arr[j]);

j++; // increment count of non-positive integers

}

}

```
return j;
```

}

int getMissing(int arr[], int size)

{

int i;

// Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that

// 1 is subtracted because index start from 0 and positive numbers start from 1

for(i = 0; i < size; i++)

{

if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0)

arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];

}

// Return the first index value at which is positive

for(i = 0; i < size; i++)

if (arr[i] > 0)

return i+1; // 1 is added becuase indexes start from 0

return size+1;

}

int firstMissingPositive(int* nums, int numsSize) {

// First separate positive and negative numbers

int shift = separateNP (nums,numsSize );

// Shift the array and call findMissingPositive for

// positive part

return getMissing(nums+shift, numsSize-shift);

}

...