First Missing Positive – Leetcode Python

by

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

Share the Knowledge