First Missing Positive Integer

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

Example:

Given [1,2,0] return 3,

[3,4,-1,1] return 2,

[-8, -7, -6] returns 1

Your algorithm should run in O(n) time and use constant space.

 /**  
  * @input A : Integer array  
  * @input n1 : Integer array's ( A ) length  
  *  
  * @Output Integer  
  */  
 int firstMissingPositive(int* arr, int n1) {  
   int left = 0, right = n1 - 1, temp, count = 0, i, k, posCount;  
   for(i = 0; i < n1; i++){  
     if(arr[i] < 0){  
       count++;  
     }  
   }  
   if(count == n1){  
     return 1;  
   }  
   count = 0;  
   while(left < right){  
     while(left < right && arr[left] > 0){  
         left++;  
     }  
     while(arr[right] <= 0){  
         right--;  
         count++;  
     }  
     if(left < right){  
       temp = arr[left];  
       arr[left] = arr[right];  
       arr[right] = temp;  
       left++;  
       right--;  
       count++;  
     }  
   }  
   if(arr[left] < 0){  
     count++;  
   }  
   posCount = n1 - count;  
   for(i = 0; i < posCount; i++){  
     k = abs(arr[i]) - 1;  
     if(arr[k] > 0 && k < posCount){  
       arr[k] = -arr[k];  
     }  
   }  
   for(i = 0; i < posCount; i++){  
     if(arr[i] > 0){  
       return i + 1;  
     }  
   }  
   return posCount + 1;  
 }