If there are queries after each insert operation, disjoint-set is able to answer each query in `O(log(alpha(n)))`

time and `O(max(element in the array))`

space, but for this problem, only one query after all the insertion finished, the time complexity should be `O(n)`

and `O(1)`

space, some simple method is in need.

Even though it is not a good idea to modify the value of the origin array, this is the only space that is available, which means it must be made used of. Then if it is possible to sort the element which is between `1...n`

, then just loop over the sorted array, the job is done.

Comparison sort is `O(n logn)`

, it is too slow. So the `bucket sort`

is the only way. As only the elements between 1...n are useful, each element `w`

should be put into the `w th`

position of the array. As it is possible there is some other element `v`

in the `w th`

position, take the `v`

out before overwriting and then iteratively use the same logic on `v`

and go on.

```
def firstMissingPositive(self, A):
n = len(A)
for index in xrange(n):
element = A[index]
while True:
if element <= 0 or element > n or element == A[element - 1]:
break
A[element - 1], element = element, A[element - 1]
for index in xrange(n):
if A[index] != index + 1:
return index + 1
return n + 1
```

Time complexity: each element is looped 2 times and swapped 1 time, so the whole time compexity is `O(n)`

Space: `O(1)`

apparently

A pure recursive `C`

solution, which has the same time and space complexity.

```
void rotate(int A[], int n, int start){
if(start <= 0 || start > n){
return;
}
if(A[start - 1] == start){
return;
}
int nxt = A[start - 1];
A[start - 1] = start;
rotate(A, n, nxt);
}
int firstMissingPositive(int A[], int n) {
int i;
for(i = 0; i < n; ++i){
rotate(A, n, A[i]);
}
for(i = 0; i < n; ++i){
if(A[i] != i + 1){
return i + 1;
}
}
return n + 1;
}
```