Question :
Given an unsorted integer array, find the smallest missing positive integer.
Example :
Input: [1,2,0]
Output: 3
Input: [3,4,-1,1]
Output: 2
Input: [7,8,9,11,12]
Output: 1
Idea :
In 1st phase, scan from left to right and mark numbers which are less than 0 and greater than n as n+1. As all the given numbers are in the range [1,n] we can use n+1.
Now all the numbers in the array are positive and is on the range [1,n+1].
In 2nd phase, if any number is found in the range [1,n] , we will attach negative sign to its corresponding index.
In 3rd phase, scan from left to right and find the first cell which is not negative and return index+1(as this is zero index based array).
Base Cases :
What if all the numbers are greater than n? Then we can simply return 1. For eg : [7,8,9,11,12]. Here all the numbers are greater than the length of the array, which is 5. In this case the first missing positive integer or the smallest missing positive integer is 1.
What if all the numbers given are within the given range i.e. [1….n], then we can simply return n+1.
Code :
`public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i
if(nums[i]<=0 || nums[i]>n){
nums[i] = n+1;
}
}
for(int i=0;i
int index = Math.abs(nums[i]);
if(index>n){
continue;
}
index --;
if(nums[index]> 0){
nums[index] = (-1)* nums[index];
}
}
for(int i=0;i
if(nums[i]>0){
return i+1;
}
}
return n+1;
}`
Code Explanation :
In the 1st phase, we iterate through the array and check if any elements are greater than n or less than or equal to zero. If any such cases, then mark the element as n+1. Now all the numbers in the array are positive.
for(int i=0;i<nums.length;i++){
if(nums[i]<=0 || nums[i]>n){
nums[i] = n+1;
}
}
In the 2nd phase, mark each element in the array by converting the index for that number as negative. So if any element is not marked as negative then its index+1 will be the missing number, as this is zero index based array. If any index is greater than n, ignore and continue with the loop.
`for(int i=0;i
int index = Math.abs(nums[i]);
if(index>n){
continue;
}
index--;
if(nums[index]> 0){
nums[index] = (-1)* nums[index];
}
}`
In the 3rd phase, we go through the array and return the index of 1st positive element.
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return i+1;
}
}
If there is no positive numbers found which also means there is no missing positive integer, then we will return n+1.
return n+1;
Time Complexity : O(n)
Aux Space : O(1)
Hope this helps! Happy coding :)
This code was inspired from Leetcoder @mor3
