```
import java.util.*;
public class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 1 is the first positive integer not in an empty list
if (n == 0)
return 1;
// We use a hash set to reduce the problem of determining if an integer is in nums to O(1) time
HashSet<Integer> numsSet = new HashSet<Integer>();
for (int i : nums) {
numsSet.add(i);
}
// There can be no more than n integers in nums, so iterate through the first integers,
// returning the first one not found in nums
for (int potential = 1; potential <= n; potential++) {
if (!numsSet.contains(potential))
return potential;
}
// The first n integers are in there, so n+1 must be the first missing positive integer
return n+1;
}
}
```