41. First Missing Positive

 

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. 

class Solution {

public int firstMissingPositive(int[] nums) {

int n= nums.length;

int i =0;

while(i < n){

int correctIdx = nums[i] - 1;

if(nums[i] > 0 && nums[i] < n && nums[i] != nums[correctIdx]){

swap(nums,i,correctIdx);

}

else{

i++;

}

}

for(int j = 0;j<n;j++){

if(nums[j] != j+1){

return j + 1;

}

}

return n + 1;

}

private void swap(int[] nums,int i,int j){

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

}

}