# 41. First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
Example 1:
Input: [1,2,0]
Output: 3
Example 2:
Input: [3,4,-1,1]
Output: 2
Example 3:
Input: [7,8,9,11,12]
Output: 1
Note:
Your algorithm should run in O(n) time and uses constant extra space.
# Solution
Approach 1: sorting takes either too much space or too much time, so can only try modifying the nums in place. Try to put the nums in their right place, but leave bad elements in there, and use a second pass to check.
# Code (Python)
Approach 1:
def firstMissingPositive(self, nums: List[int]) -> int:
# idea: also try to put the nums in their right place, but leave bad things in there, and use a second pass to check
for i in range(len(nums)):
while 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i]-1]:
self._swap(i, nums[i] - 1, nums)
for i in range(len(nums)):
if nums[i] != i + 1:
return i + 1
return len(nums) + 1
def _swap(self, ind1, ind2, nums):
temp = nums[ind1]
nums[ind1] = nums[ind2]
nums[ind2] = temp
# Code (C++)
Approach 1:
// Swap the elements to the right positions.
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i)
{
long j = long(nums[i]) - 1;
while (j >= 0 && j < nums.size() && nums[j] != nums[i])
{
std::swap(nums[j], nums[i]);
j = nums[i] - 1;
}
}
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i] != i + 1)
return i + 1;
}
return nums.size() + 1;
}
};
// Mark the positions if the corresponding elements exist.
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i] <= 0)
nums[i] = nums.size() + 1;
}
for (int i = 0; i < nums.size(); ++i)
{
int j = std::abs(nums[i]) - 1;
if (j < nums.size() && nums[j] > 0)
nums[j] = 0 - nums[j];
}
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i] > 0)
return i + 1;
}
return nums.size() + 1;
}
};