```
// O(2n) Two-pass
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) { return 1; }
for (int i = 0; i < nums.length; ) {
int realIndex = nums[i]-1;
// Not in its correct position and within bound,
// put num into its correct position
if (realIndex != i && 0 <= realIndex && realIndex < nums.length
&& nums[realIndex] != nums[i]) { // And not Duplicate
int tmp = nums[realIndex];
nums[realIndex] = nums[i];
nums[i] = tmp;
} else {
// Only keep on going if no swaps;
// Otherwise stay in place until newcomers are handled. Once max!
i++;
}
}
// First int != index, missing int
for (int i = 0; i < nums.length; i++) {
if (nums[i] != (i+1)) {
return i+1;
}
}
return nums.length + 1; // All are in sequence, next biggest
}
```