# Two easy to understand O(n) solution based on HashSet and Swap.

• The code is pretty easy to understand.

``````    public int firstMissingPositive(int[] nums) {
if(nums.length == 0){
return 1;
}
HashSet set = new HashSet();
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
max = max > nums[i] ? max : nums[i];
}
for (int i = 1; i <= max + 1; i++) {
if (!set.contains(i)) {
return i;
}
}
return -1;
}
``````

Another solution is to put every positive number into where they are supposed to be. They should be nums[i] = i + 1; If not, then swap. The inner while-loop makes sure every element gets a chance to be swapped, and nums[i] != nums[nums[i] - 1] makes sure there is no infinite loop.

``````    public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i + 1 && nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}

for (int i = 0; i < nums.length; i++) {
if (i != nums[i] - 1) {
return i + 1;
}
}
return nums.length + 1;
}

public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
``````

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