```
class Solution {
public int firstMissingPositive(int[] nums) {
int idx=0;
if(nums==null|| nums.length==0)
return 1;
/*Zero is an irrelevant number, so we convert it to negative */
for(int i=0;i<nums.length;i++)
if(nums[i]==0)
nums[i]=-1;
/*Make a demarkation for all positive integers in the array */
for(int i=0;i<nums.length;i++)
{
if(nums[i]<0)
{
int tmp=nums[idx];
nums[idx]=nums[i];
nums[i]=tmp;idx++;
}
}
/*Mark that the positive number is present by reversing the sign on the number present at its index */
for(int i=idx;i<nums.length;i++)
{
if(Math.abs(nums[i])<=nums.length)
{
if(Math.abs(nums[i])-1<idx)
nums[Math.abs(nums[i])-1]=Math.abs(nums[Math.abs(nums[i])-1]);
else
nums[Math.abs(nums[i])-1]=-Math.abs(nums[Math.abs(nums[i])-1]);
}
}
/*If the number is between 1 to n, the number present at its index is greater than 0, if it is less than idx, else it is less than
zero, if it is greater than idx. If all elements less than idx have positive sign and that greater than idx have negative sign, it means
that all numbers from 1 to n are present, so the number is n+1*/
for(int i=0;i<nums.length;i++)
{
if(i<idx && nums[i]<0)
return i+1;
if(i>=idx && nums[i]>=0)
return i+1;
}
return nums.length+1;
}
}
```