A[] is an array, but we can also treat it as an hashmap,

If A[i] > 0, it mean i+1 exist,

If A[i] < 0, it mean i + 1 does not.

Here is the code

```
class Solution {
public:
int firstMissingPositive(int A[], int n) {
/* first iteration: change all the value out of bound to (n + 1) */
const int out_of_bound = n + 1;
for (int i = 0; i < n; ++i)
if (A[i] <= 0)
A[i] = out_of_bound;
/* second iteration: construct a hash map. map<int, int>, first argument is index
* second argument: if positive, it exist, else, it doesn't. e.g. A[0] = 4,
* A[0] (i.e. 1) exist */
for (int i = 0; i < n; ++i) {
int abs_i = abs(A[i]);
if (abs_i <= n)
A[abs_i-1] = -abs(A[abs_i-1]);
}
/* third iteration: check the first positive value in A[] */
for (int i = 0; i < n; ++i) {
if (A[i] > 0)
return i + 1;
}
return n + 1;
}
};
```