Problem:
Given an array of integers find the first missing positive integer .
The first positive integer is 1.
So if 1 is itself missing you need to return 1 else whatever number after 1 is missing that should be returned.
For example,
Given the array:
[1,2,4,5]
The output is 3
Given the array:
[3,4,-1,1,5]
The output is 2
Given the array:
[1,2,3,4,5]
The output is 6 .
Constraints:
The input can contain duplicates
The input can contain negative numbers
The input can contain 0.
Try out the solution here:
https://leetcode.com/problems/first-missing-positive/
Solution:
Its a easier problem to solve in more than O(n) time complexity or more than constant space complexity.
For example, we could sort the array , ignore the negative and zero values and then start counting from 1 , whichever number is missing in the sequence we can return it.
Time complexity would be O(nlogn) for the sorting itself.
Or we can store the numbers in a hashmap .
And then look for the missing number starting from 1 in the hashmap.
Here we use extra O(n) space complexity for the map.
Let’s first look into these approaches before moving into the optimal solutions.
Approach 1: Using Sorting:
In this approach ,
We will first sort the given array.
Now the array will have negative numbers first (if present) , followed by zero if present and then by positive numbers.
We will find out the index of the first positive number.
If this number is not 1 then we return 1 as 1 should be the first positive number present.
If it is present then we keep looking for the next positive value 2,3,4 and so on until we reach the end of the array.
If any of the value is missing we return it.
Also we will ignore duplicates during this check.
If we have reached the end of the array, then it means the array has a perfect sequence starting from the value 1 up to the value of the array length.
So we will return the next value in the sequence which is the array length + 1.
here is the code:
class Solution {
public int firstMissingPositive(int[] nums) {
Arrays.sort(nums);
int tostart =0;
for(int i=0;i<nums.length;i++){
if(nums[i] <=0) tostart++;
}
//tostart index will be equal to the last index if none of the //numbers is positive, so check for that
if(tostart > nums.length -1 || nums[tostart] != 1) return 1;
for(int i=tostart+1;i<nums.length;i++){
if(nums[i] == nums[i-1]) continue;//duplicate - ignore it
if(nums[i] != nums[i-1]+1) return nums[i-1]+1;// sequence not //matched return missing number
}
return nums.length+1;
}
}
Time complexity:
Sorting the array takes O(nlogn) time complexity.
There are two for loops which each take O(n) time.
So total time complexity is O(nlogn)
Space complexity:
We dont use any extra space so space complexity is O(1)
Approach 2 – Using HashMap
In this approach we create a hash map and store all the positive numbers as keys . The value is just set to true.
Then starting from 1 we check for each value up to the array length in the map.
If any of them are not present we return it.
If all are present then we would have reached the end of the array.
In that case we will return the next element to the last element (last element plus 1).
here is the code:
class Solution {
public int firstMissingPositive(int[] nums) {
Map<Integer,Boolean> positiveMap = new HashMap<>();
for(int i:nums){
if(i > 0) positiveMap.put(i,true);
}
if(!positiveMap.containsKey(1)) return 1;
for(int i=1;i<=nums.length;i++){
if(!positiveMap.containsKey(i)) return i;
}
return nums.length + 1;
}
}
Time complexity:
We use two separate for loops so time complexity is O(2n) = O(n)
Space complexity:
We use an extra hash map of size n , so space complexity is O(n)
The last two approaches either used extra space or more than O(n) time.
The next two approaches are solutions in O(n) time complexity and O(1) space complexity.
Approach 3 – By swapping elements to their corresponding index position:
If you can put each element in the array to its corresponding index position (eg) index position of number 1 is 0 , 2 is 1 and so on)
Then we can solve this problem easily.
All you have to do after this is check if each index and the corresponding element match.
If they don’t return that element.
But first we need to do some clean up of the array.
We cannot swap negative elements into their position because you can’t have negative indexes in an array. Indexing starts from 0.
Also we don’t want the element zero.
We want to deal only with positive numbers from 1 to the array length.
So we will replace all negative numbers , the number zero and all numbers greater than the array length by the number 1.
Before that we will also check if the array has the number 1 , we will return 1 else immediately because 1 must be present.
here is the clean up code:
boolean contains = false;
for(int i:nums){
if(i == 1) contains = true;
}
if(!contains) return 1;
for(int i=0;i<nums.length;i++){
if(nums[i] < 1 || nums[i] > nums.length) nums[i] = 1;
}
Now the array has only positive numbers starting from 1.
We will start swapping elements until they are placed in their respective positions.
While swapping we need to make sure we don’t get into a loop.
This will happen if the element we are going to swap and the element present at the index corresponding to this element are the same.
Then the program will keep swapping the same values again and again and go into a loop.
So we will do the below check before the swapping:
nums[index] != nums[nums[index]-1]
Remember the value 1 will be placed in index 0, the value 2 in the index 1 and so on.
That is why there is “-1” in the above code.
Here is the swap code:
int index = 0;
while(index < nums.length){
if(nums[index] != index + 1 && nums[index] != nums[nums[index]-1]){
int t = nums[index];
nums[index] = nums[t-1];
nums[t-1] = t;
}else{
index++;
}
}
The first condition in the if loop :
nums[index] != index + 1
makes sure that you keep doing the swapping until the index is populated with the corresponding element (eg ) element 3 should be placed in index 2)
The second condition as already discussed makes sure we don’t get into a loop.
After swapping, we just go through the array and return the element which is not in its corresponding index.
Here is the entire code:
class Solution {
public int firstMissingPositive(int[] nums) {
boolean contains = false;
for(int i:nums){
if(i == 1) contains = true;
}
if(!contains) return 1;
for(int i=0;i<nums.length;i++){
if(nums[i] < 1 || nums[i] > nums.length) nums[i] = 1;
}
int index = 0;
while(index < nums.length){
if(nums[index] != index + 1 && nums[index] != nums[nums[index]-1]){
int t = nums[index];
nums[index] = nums[t-1];
nums[t-1] = t;
}else{
index++;
}
}
for(int i = 0;i<nums.length;i++){
if(nums[i] != i+1) return i+1;
}
return nums.length + 1;
}
}
Time complexity:
Time complexity is O(n) since we just iterate through the entire array four times separately irrespective of the array size.
Space complexity:
We don’t use any extra space so space complexity is O(1)
Approach 4 – Use indexes as keys by negating the numbers
In this approach instead of swapping the elements to their corresponding indexes we will just mark the corresponding index as negative.
So if an index has a negative value then it means that the element corresponding to that index is present in the array.
We use the negative symbol as a flag!
So say if there is an element 3 in the array , then whatever element is in index 2 ( index of element 3 is 2 since indexing starts from 0) , we will make it negative.
We will do the same clean up as before though.
So when we start all the elements in the array are positive.
here is the indexing logic:
int index = 0;
while(index < nums.length){
int ind = Math.abs(nums[index])-1;
nums[ind] = - Math.abs(nums[ind]);
index++;
}
We find the index of the current element (the value – 1)
And then mark the element at that index as negative.
We do Math.abs() in the above code to make sure we are always making a positive element into negative.
This is done to take care of duplicates:
Let’s say the element 3 is present twice in the array.
Then the first time we will mark the element in the index 2 as negative.
And the second time ,we will again mark it as negative.
Negative + Negative becomes positive.
To avoid that we will always take the positive value at an index and turn it into negative.
Once the negative indexing is done, we will scan through the array and return the element corresponding to the index whose value is not negative. (Not negative means that element is not in the array)
Here is that code:
for(int i = 0;i<nums.length;i++){
if(nums[i] > 0) return i+1;
}
Here is the entire code:
class Solution {
public int firstMissingPositive(int[] nums) {
boolean contains = false;
for(int i:nums){
if(i == 1) contains = true;
}
if(!contains) return 1;
for(int i=0;i<nums.length;i++){
if(nums[i] < 1 || nums[i] > nums.length) nums[i] = 1;
}
int index = 0;
while(index < nums.length){
//if(nums[index] <= nums.length){
int ind = Math.abs(nums[index])-1;
nums[ind] = - Math.abs(nums[ind]);
// }
index++;
}
for(int i = 0;i<nums.length;i++){
if(nums[i] > 0) return i+1;
}
return nums.length + 1;
}
}
As usual at the end we return nums.length +1 if all the elements in the array are in sequence.
Time complexity and Space complexity are the same as in previous approach.
That’s it!
Leave a Reply