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]
READ MORE
Python-related posts Visit HERE
C++ related posts Visit HERE
Databases related posts Visit HERE
Data Structures related posts visit HERE
Algorithms related posts visit HERE
Data Science related posts visit HERE