# leetcode: First Missing Positive

#### Problem Description:

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

For example,

Given `[1,2,0]`

return `3`

,

and `[3,4,-1,1]`

return `2`

.

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

####
Solution and **Precautions**:

Linear time usually requires hash table to do search in constant time, constant space requires we use a fixed number of variables or we directly use the input memory. Here constant space means the second case. So basically we use the input array A[] as our hash table, and by one pass through the whole array, we put each number a >= 1 and a <= n into the right position, that is a should be in position a-1, the key observation is that, the first missing positive could only be 1,….n, n+1, so basically we try to set all these positions in A to contain the right number, after this is done, we check the first slot where the position does not contain the right number, this position + 1 is the first missing positive. We can use swap or something else to do the thing that we set the position to contain the right number.