# My java solution

• as discussed elsewhere, the idea is still basically sorting, but instead of regular sorting, we kind of have radix sort here. but the value range is so big (-infinity to max) that regular radix sorting doesn't work. but the goal of the problem is not to solve everything, we just need to sort 1---A.length, if A does contain the full range. all the rest would be discarded. this would mean to sort the possible appearances of elements of A into the 1--N buckets. anything not appearing from this range would be missing.

then stated more clearly the problem becomes trying to move the N elements back to their 'original' locations, with the constraint that you can't have extra storage.

``````public class Solution {
public int firstMissingPositive(int[] A) {
int tmp;
for(int i=0;i<A.length;i++) {
// chase the chain
int ptr = A[i]-1;
while (ptr >=0 && ptr < A.length && A[ptr] != ptr +1) {
tmp = A[ptr]-1;
A[ptr] = ptr+1;
ptr = tmp;
}
}
for(int i=0;i<A.length;i++) {
if (A[i] != i+1)
return i+1;
}

return A.length+1;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.