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

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;//initialising variable

while(i < nums.length){//Applying cyclic sort, takes only 1 loop to sort
int correct = nums[i] — 1;

if(nums[i]>0 && nums[i]<nums.length && nums[i] != nums[correct]){

int temp = nums[i];
nums[i] = nums[correct];
nums[correct] = temp;
}else{
i++;//if index is correct, ignore it
}
}

//Now search for the first missing positive
for(int j = 0; j < nums.length; j++){
if(nums[j] != j + 1){
return j + 1;
}
}
return nums.length + 1;
}
}