Solution For First Missing Positive

Problem Statement:
Given an unsorted integer array nums, return the smallest missing positive integer.

Example 1:
Input: nums = [1,2,0] Output: 3

Example 2:
Input: nums = [3,4,-1,1] Output: 2

Example 3:
Input: nums = [7,8,9,11,12] Output: 1

Approach:
The approach is to use the given array as a hash table to mark the presence of the elements from 1 to n. In the array, we ignore all the negative numbers, as they cannot be part of the answer, and any number greater than n can be replaced with n, as we are only interested in the first missing positive integer. We traverse the array, and for every number in the array, we mark its presence in the hash table, placed at nums[nums[i] – 1]. Finally, we traverse the hash table, and the first index i, that does not contain i+1, is the answer.

Algorithm:
1. Traverse the given array, and place all the positive numbers, less than or equal to the length of the array, in their correct position. For any number greater than the length of the array, replace it with n+1, as we are only interested in the first missing positive integer.
2. Now, traverse the array and mark the presence of the elements in the hash table, placed at nums[nums[i] – 1].
3. Finally, traverse the hash table, and the first index i, that does not contain i+1, is the answer.
4. If no element is missing, return n+1.

Dry Run:
Let’s dry run the first example [1,2,0], for better understanding of the algorithm.

1. We traverse the array, and place all the positive numbers, less than or equal to the length of the array, in their correct position. The array becomes [1,2,0].
2. Now, we traverse the array and mark the presence of the elements in the hash table, placed at nums[nums[i] – 1]. The hash table becomes [1,1,0].
3. Finally, we traverse the hash table, and the first index i, that does not contain i+1, is the answer. Here, the answer is 3.

Solution:

class Solution {
public:
int firstMissingPositive(vector& nums) {
int n = nums.size();
//Step 1
for(int i=0;i0 && nums[i]<=n){
int pos = nums[i]-1;
if(nums[pos]!=nums[i]){
swap(nums[pos],nums[i]);
i–;
}
}
}
//Step 2
for(int i=0;i<n;i++){
if(nums[i]!=i+1){
return i+1;
}
}
//Step 3
return n+1;
}
};

Step by Step Implementation For First Missing Positive

class Solution {
    public int firstMissingPositive(int[] nums) {
        // check for the corner cases of an empty or single element array
        if (nums == null || nums.length == 0) {
            return 1;
        } else if (nums.length == 1) {
            // if the single element array contains the number 1, then return 2
            return (nums[0] == 1) ? 2 : 1;
        }
        
        // sort the array in ascending order
        Arrays.sort(nums);
        
        // check if the first element is positive and greater than 1
        if (nums[0] <= 0 || nums[0] > 1) {
            return 1;
        }
        
        // iterate through the array
        for (int i = 0; i < nums.length - 1; i++) {
            // check if the current number is positive
            if (nums[i] > 0) {
                // check if the difference between the current number and the next number is greater than 1
                if (nums[i+1] - nums[i] > 1) {
                    // return the first number that is missing
                    return nums[i] + 1;
                }
            }
        }
        
        // return the next positive number after the last element in the array
        return nums[nums.length-1] + 1;
    }
}

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        # Base case: 
        if not nums: 
            return 1 
        
        # Sort the list in ascending order 
        nums.sort() 
        
        # Edge case: If the first element is greater than 1, 
        # that means the list is not starting from 1 
        if nums[0] > 1: 
            return 1 
        
        # Iterate through the list 
        for i in range(len(nums)): 
            
            # If the current element is not equal to the previous element + 1 
            # then that element is the first missing positive number 
            if nums[i] != nums[i-1] + 1: 
                return nums[i-1] + 1
            
        # If we reach here, it means the list is starting from 1 
        # and is consecutive up till the last element 
        # Therefore, the first missing positive number is the last element + 1 
        return nums[-1] + 1

var firstMissingPositive = function(nums) {
    
    // sort the array in ascending order
    nums.sort((a, b) => a - b);
    
    // if the first element is greater than 1, then 1 is the first missing positive
    if (nums[0] > 1) {
        return 1;
    }
    
    // iterate through the array
    for (let i = 0; i < nums.length; i++) {
        // if the current element is positive
        if (nums[i] > 0) {
            // and the next element is greater than the current element + 1
            // then the current element + 1 is the first missing positive
            if (nums[i+1] > nums[i] + 1) {
                return nums[i] + 1;
            }
        }
    }
    
    // if we reach here, that means the array consists of consecutive positive integers starting from 1
    // therefore, the next integer after the last element in the array is the first missing positive
    return nums[nums.length-1] + 1;
    
};

class Solution {
public:
    int firstMissingPositive(vector& nums) {
        
        // Base case 
        if (nums.size() == 0) 
            return 1; 
  
        // To mark the presence of elements 
        // we use the sign of the elements 
        // as the index. 
        // For example, if 'n' is present 
        // at index 5, then we represent it 
        // by making the value at index -5 
        // as negative. 
        for (int i = 0; i < nums.size(); i++) { 
            int x = abs(nums[i]); 
  
            // If the index 'x-1' is positive, 
            // then make it negative to indicate 
            // that 'x' is present in the array. 
            // But if the index 'x-1' is negative, 
            // then 'x' is already present. 
            if (x > 0 && x <= nums.size()) 
                nums[x - 1] = -1 * abs(nums[x - 1]); 
        } 
  
        // If 1 is not present, then return 1 
        if (nums[0] > 0) 
            return 1; 
  
        // Find the first index value which 
        // is positive 
        for (int i = 1; i < nums.size(); i++) 
            if (nums[i] > 0) 
                return i + 1; 
  
        // If all values are negative, 
        // then the smallest positive 
        // value is size+1 
        return nums.size() + 1; 
    } 
};

public class Solution {
    public int FirstMissingPositive(int[] nums) {
        // Initialize an empty list
        List list = new List();
        
        // Loop through the input array
        for(int i = 0; i < nums.Length; i++) {
            // If the current element is positive, add it to the list
            if(nums[i] > 0) {
                list.Add(nums[i]);
            }
        }
        
        // Sort the list in ascending order
        list.Sort();
        
        // Loop through the sorted list
        for(int i = 0; i < list.Count; i++) {
            // If the current element is not equal to its index + 1,
            // then that is the first missing positive integer
            if(list[i] != i + 1) {
                return i + 1;
            }
        }
        
        // If we reach here, that means the list is complete
        // without any missing integers, so return the next integer
        return list.Count + 1;
    }
}