My 0ms C++ recursive Solution

• This solution is similar with makuiyu's solution but go through the vector in a reverse order.m is to record the newest position that has the wrong number. So that we dont need to go through the vector twice.

``````	int firstMissingPositive(vector<int>& nums) {
int m = nums.size();

for (size_t i = nums.size(); i != 0; --i){
if (!traceFinder(nums, i - 1, m))
m = i - 1;
}
return m + 1;
}
bool traceFinder(vector<int>& nums, size_t n, size_t m){
if (nums[n] > m || nums[n] < 1)
return false;
else if (nums[n] == n + 1)
return true;
else if (nums[nums[n] - 1] == nums[n])
return false;
else{
swap(nums[n], nums[nums[n] - 1]);
return traceFinder(nums, n, m);
}
}
``````

Because it is a recursive way, O(n) space is needed. You can rewrite it in a non-recursive way like this which is a little bit slower.

``````int firstMissingPositive(vector<int>& nums) {
int m = nums.size();

for (size_t i = nums.size(); i != 0; --i){
while (nums[i-1] <= m && nums[i-1] >= 1 && nums[i-1] != i && nums[nums[i-1] - 1] != nums[i-1])
swap(nums[i-1], nums[nums[i-1] - 1]);
if (nums[i-1] != i)
m=i-1;
}
return m + 1;
}
``````

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