## Algorithm

Problem Name: 41. First Missing Positive

Given an unsorted integer array `nums`, return the smallest missing positive integer.

You must implement an algorithm that runs in `O(n)` time and uses constant extra space.

Example 1:

```Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
```

Example 2:

```Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
```

Example 3:

```Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.
```

Constraints:

• `1 <= nums.length <= 105`
• `-231 <= nums[i] <= 231 - 1`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int firstMissingPositive(int* nums, int numsSize) {
int i, k, t;
for (i = 0; i  <  numsSize; i ++) {
k = nums[i];
while (k > 0 && k  <  numsSize && k != nums[k - 1]) {
nums[i] = nums[k - 1];
nums[k - 1] = k;
k = nums[i];
}
}
for (i = 0; i  <  numsSize; i ++) {
if (nums[i] != i + 1) break;
}
return i + 1;
}

``````
Copy The Code &

Input

cmd
nums = [1,2,0]

Output

cmd
3

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
sort(nums.begin(), nums.end());
int i = 1;
for(int x: nums) if(x == i) i++;
return i;
}
};

``````
Copy The Code &

Input

cmd
nums = [3,4,-1,1]

Output

cmd
2

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
int idx = 0;
while (idx  <  n) {
if (nums[idx] > 0 && nums[idx] < n && nums[nums[idx]] != nums[idx]) {
swap(nums, idx, nums[idx]);
}
else {
idx++;
}
}
idx = 1;
while (idx  <  n && nums[idx] == idx) {
idx++;
}
if (n == 0 || idx < n) {
return idx;
}
return nums[0] == idx ? idx + 1 : idx;
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
``````
Copy The Code &

Input

cmd
nums = [7,8,9,11,12]

Output

cmd
1

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const firstMissingPositive = function(nums) {
if(nums.length === 0) return 1
const arr = []
let max = Number.MIN_SAFE_INTEGER
for(let i = 0, len = nums.length; i < len; i++> {
if(nums[i] > 0) arr[nums[i]] = nums[i]
if(nums[i] > max) max = nums[i]
}
for(let i = 1; i < max; i++) {
if(arr[i] == null> return i
}
return max  <  0 ? 1 : max + 1
};
``````
Copy The Code &

Input

cmd
nums = [1,2,0]

Output

cmd
3

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def firstMissingPositive(self, nums: List[int], res: int = 1) -> int:
for num in sorted(nums):
res += num == res
return res
``````
Copy The Code &

Input

cmd
nums = [3,4,-1,1]

Output

cmd
2

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _041_FirstMissingPositive
{
public int FirstMissingPositive(int[] nums)
{
int i, temp;
for (i = 0; i  <  nums.Length; i++)
{
temp = nums[i];
while (temp > 0 && temp  <  nums.Length && nums[temp - 1] != temp)
{
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
temp = nums[i];
}
}

for (i = 0; i  <  nums.Length; i++)
{
if (nums[i] != i + 1) { break; }
}
return i + 1;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [7,8,9,11,12]

Output

cmd
1