# First Missing Positive

#1

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

Example 1:

```Input: [1,2,0]
Output: 3
```

Example 2:

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

Example 3:

```Input: [7,8,9,11,12]
Output: 1
```

Note:

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

#2

Since the output is expected to be the smallest missing positive number, the value is expected to be between `0` and `n`. The below code will put the numbers from `0` to `n` in each of their respective places and finds out the missing number in the second pass. If we don’t find it, we return `n+1`.

``````class Solution {
public int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0) return 1;          //case: nums == null or nums == [], return 1
for(int i = 0;i < nums.length;i++){                     //use nums array itself, the ideal array should be {1,2,3,4}
int curr = nums[i];                                 //swap if nums[index] != index + 1;
while(curr - 1 >= 0 && curr - 1 < nums.length && curr != nums[curr-1]){
int next = nums[curr-1];
nums[curr-1] = curr;
curr = next;
}
}
for(int i = 0;i< nums.length;i++){                      //check if nums[index] == index + 1;
if(nums[i] != i+1) return i+1;
}
return nums.length+1;                                   //corner case: {1,2,3,4} return 5
}
}
``````