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;
}
Input
Output
#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;
}
};
Input
Output
#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;
}
}
Input
Output
#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
};
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output