Lets Code Everyday

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-in Arrays.sort() method.
A Set object set 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 array nums.
For each positive integer num in the input array, it is added to the set object to store unique values.
The List object list is created to store the unique positive integers from the set 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 the list.
For each positive integer i in the list, it is compared to the start variable to check if it is the expected positive integer. If i is equal to start, then the start variable is incremented by 1 to check the next expected positive integer.
If i is not equal to start, it means that start is the smallest positive integer that is not present in the input array. Therefore, the res variable is set to start, and the loop is terminated using the break 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 of res, 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 called set to store the elements in the input array nums.
Create a long variable max 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 the max variable if the current element is greater than max.
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 integer i. If i is not in the HashSet, 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....😁

Thanks for commenting 😁 & giving another possibility to solve the problem.

If I understood correctly ,The approach you described involves dividing the array and checking the last element of the left subarray to determine if there are positive numbers in that subarray. If the last element is positive, the algorithm recursively searches that subarray. Otherwise, it searches the right subarray.

I don't think there will be variation in time complexity since sorting involves in the suggested approach also.

But will definitely try the approach mentioned via code and get back.

Actually the first approach taken is to solve the problem mainly. Then after I have focused on decreasing complexity in terms of time and space. Unfortunately ended up in bringing difference in only time complexity in second approach i.e., O(n) which is better than first approach with time complexity i.e., O(nlogn)