41. First Missing Positive(Solution || Leetcode hard || Java)

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.

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.

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

SOLUTION:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        
        //we are going to apply cycle sort here to sort thr array
        while(i < nums.length){
           int correct = nums[i] - 1;
            
            //if the number is negative or greater then array's length
        // then skip that number
            if(nums[i] > 0 && nums[i] <= nums.length && nums[i] != nums[correct]){
               swap(nums,correct,i);
            }else{
                i++;
            }
        }
        
        for(int j = 0; j < nums.length; j++){
            if(nums[j] != j+1){
                return j+1;
            }
        }
        
        return nums.length +1;
    }
    
    public void swap(int[] nums, int first, int second){
        int temp = nums[first];
        nums[first] = nums[second];
        nums[second] = temp;
    }
}

Runtime: 2 ms, faster than 86.27% of Java online submissions for First Missing Positive.

Memory Usage: 57.8 MB, less than 44.58% of Java online submissions for First Missing Positive.

Thank you for reading. If you have any queries then, pleaselet me know in the comment section. I will surely be responsive toward it.