Question - 22:
First Missing Positive
Given an unsorted integer array nums
, return the smallest missing positive integer.
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.
First approach:
class Solution {
public int firstMissingPositive(int[] nums) {
Arrays.sort(nums);
Set<Integer> set = new LinkedHashSet<>();
int start=1;
int res=0;
if(nums.length==1 && nums[0]==0) return 1;
for(int num:nums) {
if(num>0) set.add(num);
}
List<Integer> list = new ArrayList<>(set);
if(list.size()==0) return 1;
for(int i:list){
if(i==start) start++;
else{
res=start;
break;
}
}
return (res==0) ? list.get(list.size()-1)+1:res;
}
}
Step-by-step implementation:
The method begins with sorting the input array
nums
in ascending order using the built-inArrays.sort()
method.A
Set
objectset
is created to store the unique positive integers from the sorted input array.The variable
start
is initialized to 1, which represents the first positive integer that is expected to be present in the input array.The variable
res
is initialized to 0, which represents the default return value of the method.A special case is handled for the input array with length 1 and the only element is 0. In this case, the method returns 1, as 1 is the smallest positive integer that is not present in the input array.
A for-each loop is used to iterate over each element
num
in the sorted input arraynums
.For each positive integer
num
in the input array, it is added to theset
object to store unique values.The
List
objectlist
is created to store the unique positive integers from theset
object.Another special case is handled if the
list
is empty, which means there are no positive integers in the input array. In this case, the method returns 1, as 1 is the smallest positive integer.A for-each loop is used to iterate over each positive integer
i
in thelist
.For each positive integer
i
in thelist
, it is compared to thestart
variable to check if it is the expected positive integer. Ifi
is equal tostart
, then thestart
variable is incremented by 1 to check the next expected positive integer.If
i
is not equal tostart
, it means thatstart
is the smallest positive integer that is not present in the input array. Therefore, theres
variable is set tostart
, and the loop is terminated using thebreak
statement.Finally, the method returns the smallest positive integer that is not present in the input array. If
res
is equal to 0, it means that all the positive integers up to the largest integer in the input array are present, and the method returns the next integer after the largest integer in the input array. Otherwise, it returns the value ofres
, which is the smallest positive integer that is not present in the input array.
Time Complexity:
Sorting the input array takes O(n*log n) time where n is the length of the array.
Iterating over the input array to add positive integers to the set takes O(n) time.
Converting the set to a list takes O(k) time where k is the number of unique positive integers in the input array.
Iterating over the list to find the first missing positive integer takes O(k) time in the worst case.
Therefore, the overall time complexity of the method is O(n*log n + k).
Space Complexity:
A set is used to store the unique positive integers from the input array. The worst-case size of the set is n, so the space complexity is O(n).
A list is created to store the unique positive integers from the set, which takes O(k) space.
Other variables such as
start
,res
, and loop counters use constant space.
Therefore, the overall space complexity of the method is O(n).
Second approach:
class Solution {
public int firstMissingPositive(int[] nums) {
Set<Integer> set = new HashSet<>();
long max=1;
for(int num:nums){
set.add(num);
max=Math.max(num,max);
}
for(int i=1;i<=max+1;i++){
if(!set.contains(i)) return i;
}
return 0;
}
}
Step-by-step implementation:
Create a new
HashSet
calledset
to store the elements in the input arraynums
.Create a
long
variablemax
and initialize it to 1. This variable will be used to find the maximum element in the input array.Iterate over the elements in the input array
nums
.Add each element to the
HashSet
set
.Find the maximum element in the input array
nums
by comparing each element to the current maximum value and updating themax
variable if the current element is greater thanmax
.End the loop over the elements in the input array
nums
.Iterate over a range of integers from 1 to the maximum element in the input array
nums
plus one.Check if the
HashSet
set
contains the current integeri
. Ifi
is not in theHashSet
, then it is the smallest missing positive integer and should be returned.End the loop over the range of integers.
If no missing positive integer is found, return 0 as the default value.
The time complexity of the given code is O(n), where n is the length of the input array. This is because the code iterates over the input array once to add all the elements to a HashSet and to find the maximum value, and then iterates from 1 to the maximum value in the array + 1 to find the smallest missing positive integer.
The space complexity of the code is also O(n), because the HashSet used to store the input array has a space complexity proportional to the number of elements in the array. Additionally, the code uses a variable to store the maximum value in the array, which has a space complexity of O(1).
Conclusion:
Therefore the second approach performs better in terms of both time and space complexity compared to the first approach.
Happy learning....๐