41_First_Missing_Positive

Leetcode 41: First Missing Positive
Detailed video Explanation: https://youtu.be/L1u-R_s2Mok
======================================

C++:
----
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        bool contains_one = false;
        for(int x: nums){
            if(x == 1){
                contains_one = true;
                break;
            }
        }
        if(!contains_one) return 1;
        
        int n = nums.size();
        if(n == 1) return 2;
        
        for(int i = 0; i < n; ++i)
            if(nums[i] <= 0 || nums[i] > n) nums[i] = 1;
        
        for(int i = 0; i < n; ++i){
            int x = abs(nums[i]);
            if(nums[x-1] > 0) nums[x-1] *= -1;
        }
        
        for(int i = 0; i < n; ++i)
            if(nums[i] > 0) return i+1;
        
        return n+1;
    }
};




Java:
-----
class Solution {
    public int firstMissingPositive(int[] nums) {
        boolean contains_one = false;
        for(int x: nums){
            if(x == 1){
                contains_one = true;
                break;
            }
        }
        if(!contains_one) return 1;
        
        int n = nums.length;
        if(n == 1) return 2;
        
        for(int i = 0; i < n; ++i)
            if(nums[i] <= 0 || nums[i] > n) nums[i] = 1;
        
        for(int i = 0; i < n; ++i){
            int x = Math.abs(nums[i]);
            if(nums[x-1] > 0) nums[x-1] *= -1;
        }
        
        for(int i = 0; i < n; ++i)
            if(nums[i] > 0) return i+1;
        
        return n+1;
    }
}




Python3:
-------
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        contains_one = False
        for x in nums:
            if x == 1:
                contains_one = True
                break
        
        if not contains_one: return 1
        
        n = len(nums)
        if n == 1: return 2
        
        for i in range(n):
            if nums[i] <= 0 or nums[i] > n: nums[i] = 1
        
        for i in range(n):
            x = abs(nums[i])
            if nums[x-1] > 0: nums[x-1] *= -1
        
        for i in range(n):
            if nums[i] > 0: return i+1
        
        return n+1