First Missing Positive – Leetcode Python

LeetCode has a Hard coding Problem in Its’ Algorithm Section “First Missing Positive”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

Question

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.

Examples

```Input: nums = [1,2,0]
Output: 3
```
```Input: nums = [3,4,-1,1]
Output: 2
```
```Input: nums = [7,8,9,11,12]
Output: 1
```

Constraints:

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

Solution to First Missing Positive

The Skeleton Code given by LeetCode is

``````class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
``````

Complete Solution:

``````class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
for i in range(n):
# To determine whether this number can be exchanged
while nums[i]>0 and nums[i]<=n and nums[i]!=nums[nums[i]-1]:
self.swap(nums,i,nums[i]-1)
for i in range(n):
if nums[i]!=i+1:
return i+1
return n+1
def swap(self,nums,i,j):
nums[i],nums[j] = nums[j],nums[i]``````