First Missing Positive

Given an unsorted integer array nums, find 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

Constraints:

• 0 <= nums.length <= 300

• -231 <= nums[i] <= 231 - 1

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space?

Solution:

class Solution {
   public int firstMissingPositive(int[] nums) {
    if(nums.length==0) return 1;
    int lastPositiveindex=partition(nums)+1;
           
    for(int i=0;i<lastPositiveindex;i++){
       int k=Math.abs(nums[i]);
        if(k<=lastPositiveindex)
            nums[k-1]=(nums[k-1]<0)?nums[k-1]:-nums[k-1];
    }
    for(int i=0;i<lastPositiveindex;i++){
        if(nums[i]>0){
            return i+1;
        }
    }
    return lastPositiveindex+1;
}

public int partition(int[] nums)
{
    int j=-1;
    for(int i=0;i<nums.length;i++){
        if(nums[i]>0){
            j++;
            int temp = nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
    }
    return j;
}
}