# A hashmap based solution, but in-place

• 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;
}
};``````

• I think in your code A[i] < 0 means i + 1 exist.

• Thx for sharing, I think I've learned a new skill from your code. :)

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