https://leetcode.com/problems/first-missing-positive/

Based on this intuition, try solving on our own before looking at the code.

If we have an array of length n we know "smallest missing positive integer" must be in between 1 and n+1(inclusive).

For example:
[3,1,2,8,9] in this case we have an array of length n=5, so our smallest missing positive integer must lie between 1 and 5+1 = 6(inclusive).

Clearly, those values that are greater than n(5) should not be in here. Because if we have any value greater than n those values are occupying some smaller values place. For example, 8 is occupying index 3 where we should have either 4 or 5 and also 9 is occupying index 4 where we should have either 5 or 4.

The same goes for any value less than or equal to 0.

For example:
[-1,-2,3,1,2]
-1 is at index 0 where we should either 4 or 5, the same is true for -2 as well.

So, values that are >n and <=0 are all garbage. We don't need those.

Let's modify the array:
[3,1,2,8,9] will become [3,1,2,1,1]
[-1,-2,3,1,2] will become [1,1,3,1,2]

Why are we putting 1 in place of those values?

We know that, 1 is the smallest positive integer from 1 to infinity.

So if our array does not contain 1 then we know for sure that 1 is going to be the answer. There is no point checking further.

But, if we do have 1 as an item inside the array then some other value[ >1 && <=n ] inside the array which is missing will be the answer. If none are missing then n+1 will be the answer.

With that in mind when we see any garbage value that should not be in this array we replace that value with 1, which we already knew is present in the array. Between garbage value and 1, only 1 is allowed to be present in our modified array.

Once we are done processing our array, we know all the values inside the array should lie between 1 & n(inclusive).

One more processing needs to happen before we look for the answer.
As an easier example, let's say after processing up till this point we got an array like this:
[1,2,3,3]
In an ideal case we should have had [1,2,3,4], if all the values were present. Now in this case which one is not present? How can you tell?
If we take each value of each index and update the corresponding value to it's negative then we will have an array like this [-1,-2,-3,3].
How? Take i=2, update whatever is present to negative:

``````                int index = Math.abs(nums[i])-1;
nums[index] = -Math.abs(nums[index]);
``````

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

After that, we will check for the first index where the value is still positive. Our answer will be that index+1.

If this is not the case then our answer will be n+1 since all the values between 1 and n are present in the array.

Hope this will help anyone who is not looking for code but explanation.

## Solution[Java]:

``````    public int firstMissingPositive(int[] nums) {
boolean oneFound = false;
for(int a:nums){
if(a==1){
oneFound = true;
break;
}
}

if(oneFound){
int n = nums.length;
for(int i=0;i<n;i++){
if(nums[i]<=0 || nums[i]>n){
nums[i] = 1;
}
}

for(int i=0;i<n;i++){
int index = Math.abs(nums[i])-1;
nums[index] = -Math.abs(nums[index]);
}

for(int i=0;i<n;i++){
if(nums[i]>0){
return i+1;
}
}

return nums.length+1;
}else{
return 1;
}
}``````