Java Solution with iteration and in-place

• Goal: each positive integer p should be placed at index p-1; in the end, iterate from index=0 to right, stop at the first index whose value is non-positive; and return the missing integer as index+1.

To achieve this:

1. Iterate through the array.
2. If current element, 'curr', is positive and its value is not equal to index+1, move it to index+1.
3. If there is another positive integer at index+1, continue moving that integer.
4. After moving curr to the right location, reset this index to 0.
5. In the end, iterate from index 0 to right, stop at first index with non-positive value. return index+1.
``````    public int firstMissingPositive(int[] A) {
for (int i = 0; i < A.length; i++) {
if (A[i] > 0 && A[i] != i+1) {
int curr = A[i];
A[i] = 0;
while (curr > 0 && curr-1 < A.length) {
int next = A[curr-1];
A[curr-1] = curr;
if (curr != next)   // have to check this, otherwise infinity loop
curr = next;    // continue placing next at right index, if it's positive.
else
curr = 0;
}
}
}
// look for first index with non-positive value
for (int i = 0; i < A.length; i++) {
if (A[i] <= 0)
return i+1;
}
return A.length + 1;
}``````

• Your code is too complex. Loo at my code below:

``````public int firstMissingPositive(int[] A) {
if (A == null || A.length == 0) {
return 1;
}

// Put the corresponding positive value in the index that equals to its value
int len = A.length;
for (int i = 0; i < len;) {
int num = A[i];
if (num > 0 && num < len && num != i && num != A[num]) {
A[i] = A[num];
A[num] = num;
} else {
++i;
}
}

// Scan the array to find the first value that is not equal to its index, then it is the missing value
// Test small examples first
int missingValue = A[0] == len ? len+1 : len;
for (int i = 1; i < len; ++i) {
if (A[i] != i) {
missingValue = i;
break;
}
}

return missingValue;
}``````

• if (num > 0 && num < len && num != i && num != A[num]) can be
if (num > 0 && num < len && num != A[num])

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