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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	-231 &lt;= nums[i] &lt;= 231 - 1


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        mn = float('inf')
        mx = 0
        numsSet = set()

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] > 0:
                if nums[i] < mn:
                    mn = nums[i]
                if nums[i] > mx:
                    mx = nums[i]
                numsSet.add(nums[i])
            del nums[i]

        if mn >= 2:
            return 1
        if len(numsSet) == mx:
            return mx + 1
        for i in range(2, len(numsSet) + 1):
            if i not in numsSet:
                return i
class Solution {
   public int firstMissingPositive(int[] nums) {
       //cyclic sort
        int i = 0;
        while (i<nums.length){
            int correct = nums[i]-1;
            if(nums[i]>0 && nums[i]<=nums.length && nums[i]!=nums[correct]){
                swap(nums,i,correct);
            }else{
                i++;
            }
        }
       //linear search to find the missing number
        for(int index=0;index<nums.length;index++){
            if (nums[index] != index+1) {
                return index+1;
            }
        }
       //if array has all the elements match to its index then 1st missing num will be
       //nums.length+1
        return nums.length+1;
    }
    static void swap(int[]arr,int a , int b){
        int temp = arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i=0; i<n; i++){
            if(nums[i]==i+1 || nums[i]<=0 || nums[i]>n) continue;
            while(nums[i]!=i+1 && nums[i]>0 && nums[i]<=n && nums[nums[i]-1] != nums[i]){
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        int ans = -1;
        for(int i=0; i<n; i++){
            if(nums[i]!=i+1){
                ans = i+1;
                break;
            }
        }
        if(ans==-1){
            return n+1;
        }else{
            return ans;
        }
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {

    //first make all negative numbers to zero =>zero means we ignore whis number
    for (let index = 0; index < nums.length; index++) {
        if (nums[index] < 0)
            nums[index] = 0
    }

    for (let index = 0; index < nums.length; index++) {
        const temp = Math.abs(nums[index])
        const element = temp - 1

        if (element < nums.length && element >= 0)
            nums[element] = nums[element] === 0 ? -(nums.length + 1) : Math.abs(nums[element]) * -1

    }

    for (let index = 0; index < nums.length; index++) {
        const element = (nums[index])
        if (element >= 0) return index + 1

    }
    return nums.length+1

};
First Missing Positive