Find the smallest positive number missing from an unsorted array

You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space.

Example:
Input = {2, 3, 4, 6, 8, -1, -3}
Output = 1

Input = { 1, 3, -7, 6, 8, 1, -5, 5 }
Output = 2

We can use sorting. We can sort the array in O(nLogn) time. Once the array is sorted, then all we need to do is a linear scan of the array. So this approach takes O(nLogn + n) time.

O(N) solution:
Algorithm:
1) Segregate positive and negative numbers i.e. move all negative numbers to left side.
2) Now we can ignore negative elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. During traversing, we can ignore the index value if it is greater than array size. We are bothered only for array values in range of array size.

/* put all 0 and negative numbers on left 
  side of array and return count of such numbers */
int segregate (int arr[], int n)
{
    int j = 0, i;
    for(i = 0; i < n; i++)
    {
       if (arr[i] <= 0)  
       {
           swap(&arr[i], &arr[j]);
           j++;  
       }
    }
 
    return j;
}
 
/* Find the smallest positive missing number in an array */
int findPositive(int arr[], int n)
{
  int i;
 
  // Mark arr[i] as visited by making arr[arr[i] - 1] negative.
  for(i = 0; i < n; i++)
  {
    if(abs(arr[i]) - 1 < n && 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 < n; i++)
    if (arr[i] > 0)
      return i+1;
 
  return n+1;
}
 
/* Find the smallest positive missing number  */
int findMissing(int arr[], int len)
{
   // First separate positive and negative numbers
   int neg = segregate (arr, n);
   return findPositive(arr+neg, len-neg);
}