# O(1) space, O(N) time, no partition, no sorting solution

• Assume the length of the input array is N.
We are only interested in the value in the range of 1 to N, all other values (zero, negative, bigger than N) are not our concern. Because if there is one positive number missing, it lies in between 1 to N, or no positive number is missing, in that case we return N + 1.
Algorithm is to exchange all interesting numbers (1 to N) to its correct position, where correct position means position val - 1 for value val (array index zero based).

Therefore, condition to exchange for a number val:

1. val > 0;
2. val <= N;
3. val is not in its correct position;
4. the position we want to move val to does not have the correct number (otherwise, incase of duplicate numbers, the 2 numbers will exchange forever, think about the test case {1, 1}).

Code:

``````public class Solution {
public static int firstMissingPositive(int[] nums) {
int n = nums.length;
int curIdx = 0;
while (curIdx < n) {
int cur = nums[curIdx];
if (cur <= 0 || cur > n || cur == curIdx + 1
|| nums[cur - 1] == cur) {
// out of range numbers, or already in the correct position, or
// target position already has the correct number
curIdx += 1;
continue;
} else {
// exchange to the correct position
nums[curIdx] = nums[cur - 1];
nums[cur - 1] = cur;
}
}

int ret = 1;
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
ret = i + 1;
return ret;
}
}
// all number are in the correct position, return the next bigger
// integer
return n + 1;
}
}
``````

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