## Finding the 1st missing positive int in an array (First Missing Positive)

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in $O(n)$ time and uses constant space.

Thoughts:
The idea is simple. What is the most desired array we want to see? Something like [1,2,3] then we know 4 is missing, or [1, 8, 3, 4] then we know 2 is missing. In other word, “all the numbers are in their correct positions”. What are correct positions? For any $i$, A[i] = i+1. So our goal is to rearrange those numbers (in place) to their correct positions. We then need to decide how to arrange them. Let’s take the [3, 4, -1, 1] as an example. The 1st number, 3, we know it should stay in position 2. So we swap A[0] = 3 with A[2]. We then get [-1, 4, 3, 1]. We can’t do anything about -1 so we leave it there. The 2nd number, 4, we know it should sit in A[3]. So we swap A[1] = 4 with A[3]. We then get [-1, 1, 3, 4]. Now 1 should stay in A[0], so we keep swapping and we get [1, -1, 3, 4]. Notice now every positive number is staying in their correct position (A[0]=1, A[2]=3 and A[3]=4). We then need one more scan to find out 2 is missing.

Code (Java):

```import java.util.HashSet;
public class Solution {
public int firstMissingPositive(int[] A) {
for(int i = 0; i < A.length; ++i) {
while(A[i] != i + 1) {
if(A[i] <= 0 || A[i] > A.length || A[i] == A[A[i]-1])
break;
int temp = A[i];
A[i] = A[temp - 1];
A[temp - 1] = temp;
}
}

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

Code (C++):
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for(int i = 0; i < n; ++i) {
while(A[i] != i + 1) {
if(A[i] <= 0 || A[i] > n || A[i] == A[A[i]-1])
break;
int temp = A[i];
A[i] = A[temp - 1];
A[temp - 1] = temp;
}
}
for(int i = 0; i < n; ++i)
if(A[i] != i+  1)
return i + 1;
return n + 1;
}
};

div.wpmrec2x{max-width:610px;}
div.wpmrec2x div.u > div{float:left;margin-right:10px;}
div.wpmrec2x div.u > div:nth-child(3n){margin-right:0px;}

(function(g,\$){if("undefined"!=typeof g.__ATA){
}})(window,jQuery);

var o = document.getElementById('crt-334031200');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}

var o = document.getElementById('crt-1855168512');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}