In this guide we will provide 41. First Missing Positive LeetCode Solution with best time and space complexity. The solution to First Missing Positive problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary 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.
41. First Missing Positive LeetCode Solution in C++
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
const int n = nums.size();
// Correct slot:
// nums[i] = i + 1
// nums[i] - 1 = i
// nums[nums[i] - 1] = nums[i]
for (int i = 0; i < n; ++i)
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
swap(nums[i], nums[nums[i] - 1]);
for (int i = 0; i < n; ++i)
if (nums[i] != i + 1)
return i + 1;
return n + 1;
}
}; /* code provided by PROGIEZ */
41. First Missing Positive LeetCode Solution in Java
class Solution {
public int firstMissingPositive(int[] nums) {
final int n = nums.length;
// Correct slot:
// nums[i] = i + 1
// nums[i] - 1 = i
// nums[nums[i] - 1] = nums[i]
for (int i = 0; i < n; ++i)
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
swap(nums, i, nums[i] - 1);
for (int i = 0; i < n; ++i)
if (nums[i] != i + 1)
return i + 1;
return n + 1;
}
private void swap(int[] nums, int i, int j) {
final int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
} // code provided by PROGIEZ
41. First Missing Positive LeetCode Solution in Python
class Solution:
def firstMissingPositive(self, nums: list[int]) -> int:
n = len(nums)
# Correct slot:
# nums[i] = i + 1
# nums[i] - 1 = i
# nums[nums[i] - 1] = nums[i]
for i in range(n):
while nums[i] > 0 and nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i, num in enumerate(nums):
if num != i + 1:
return i + 1
return n + 1 #code by PROGIEZ
