In this post, you will know how to solve the First Missing Positive Leetcode Solution of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
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
First Missing Positive Leetcode Solutions 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
First Missing Positive Leetcode Solutions in CPP
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;
}
};
First Missing Positive Leetcode Solutions 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;
}
}
Note: This problem First Missing Positive is is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Next: Search in Rotated Sorted Array Leetcode Solution
