Given an unsorted integer array, find the smallest missing positive integer.

Input: [ 2, 3, -1, -2]
Output: 1

Input: [5, 6, 7, 8, 9]
Output: 1

The solution is actually very simple.  And we know that an integer starts with 1 to n not zero.

Hence what we do is, first count the number of elements in the array. Suppose we have an array with “n” elements.

We follow below steps to get the result:

Step 1:
	Iterate through out the array
	Set current_value = arr[i]
		If current_value < 0 and current_value > array_length
			Ignore and continue
		Else
			Set current_value to the index, whose value is equal to current_value

Step 2:
	Once completed step 1, iterate throughout the array 
        to find which smallest index is not having value. You will get your missing element.

Input:
	[2, 3, -1, -2]

Pass 1:
	Current_value = 2
		2 > 0 && 2 > 4 true
		swap 2 and -1
		resulting array:
		[-1, 3, 2, -2]

Pass 2:
	Current_value = 3
		3> 0 && 3 > 4 true
		swap 3 and -2
		resulting array:
		[-1, -2, 2, 3]

Pass 3:
	Current_value = 2
		2> 0 && 2 > 4 true
		as 2 is in already at it’s index, leave it.
		resulting array:
		[-1, -2, 2, 3]

Pass 4:
	Current_value = 3
		3> 0 && 3 > 4 true
		as 3 is in already at it’s index, leave it.
		resulting array:
		[-1, -2, 2, 3]

Finally iterating through out the array:

We find out that the first index i.e arr[1] !=  1. Hence the lowest missing element is 1.

#include<stdio.h>

int firstMissingPositive(int arr[], int length) {
	int n = length;
	int itr = 0;
	for ( itr = 0; itr < n; itr++) {

		while (arr[itr] != itr) {
			// we shall swap for only +ve integers and is less than the length of the array
			if (arr[itr] <= 0 || arr[itr] >= n)
				break;
 
			//handle duplicate elements
			if(arr[itr] == arr[ arr [ itr ] ] )
			{
                break;
            }

			// swap elements
			int temp = arr[itr];
			arr[itr] = arr[temp];
			arr[temp] = temp;
		}
	}
 
 // start the "itr" value from 0, if you want to consider 0 as smallest +ve integer.
	for (int itr = 1; itr < n; itr++) {
		if (arr[itr] != itr)
			return itr;
	}
	return n;
}


int main()
{
	int arr [100] = {2,1,4,5,6};
	int length = 5;
	int firstMissingPositiveInteger = 0;

	firstMissingPositiveInteger = firstMissingPositive(arr, length);

	printf("The smallest missing positive integer is = %d\n", firstMissingPositiveInteger );

}