First Missing Positive Java Explained


  • 0
    S

    This was the simplest way i found after struggling for a bit.. What one must realize is that we can use the given array to store our positive integers at their corresponding index. What I mean by this is if you have the value 3 you would store it at i = 3-1. Since we are dealing with only positive integers we forget about 0 completely and use index 0 to store value 1, index 1 to store value 2, index 2 to store value 3 etc... Forgetting about any positive integers that do not fall within the size of the given array as they do not matter for the purpose of finding the first Missing Positive. This is because even if we have a large int value that does not fall within the array size the first missing positive must fall within the array size.

    For Example if we have [1000, 1].. Then our array is of size 2 and can hold two values
    1 at index 0 and 2 at index 1. if we place each value in our array that corresponds to
    an index we would place 1 at index 0 and 1000 could not place to a corresponding index. So then after placing all positive values that could be place to corresponding indexes, we would find that at index 0 we have 1 which is what is expected but at index 1 there would be no value 2 which is what is expected. This then means our first missing positive value is 2.

    Similarly this would work for any scenario. if for example after placing all positive values in their corresponding indexes, index 0 did not contain value 1 then the first missing value is 1.. This would be the case if you were given an array with all negative values for example [-1,-2,100, -1].. You would go through the whole array and place all positive values in their corresponding indexes, but since there are no positive values then you then you would essentially leave the given array untouched and when looking at it to find the first index that does not have its corresponding value, you would notice that index 0 does not have 1 as the corresponding value and you would return 1 as the first missing positive value.

    The two exceptions to this are and empty array.. where you would not be able to add any value to indexes as the array is of size zero and thus has no indexes in this case you would know to return 1 since that is the first missing positive value when you have no positive values.

    The second exemption is you found all values corresponded to the given array at each index this mean every positive value is present for the size of the array such as if given [3,1,2] which you would transform to [1,2,3]. In this case you would then return the size of the array plus one since the next positive value would be one plus the size of the array..

    Bellow you will find the code that looks through the given array, places every positive value that is within the size of the array to its corresponding index. Then looks through the array and finds the first index that does not have a corresponding value to it, returning the value corresponding to that index as the First Missing Positive Number.

    public int firstMissingPositive(int[] nums) {
            for(int i = 0; i < nums.length; i++){
                while((nums[i] > 0 && nums[i] <= nums.length) && (nums[i]-1) != i){
                    int temp = nums[nums[i]-1];
                    if(nums[nums[i]-1] != nums[i]){
                        nums[nums[i]-1] = nums[i];
                        nums[i] = temp;
                    }
                    else{
                        nums[i] = nums.length + 1;
                    }
                    
                }
            }
            
            for(int i =0; i< nums.length; i++){
                if(nums[i] -1 != i){
                    return i+1;
                }
            }
            if(nums.length == 0){
                return 1;
            }
            else{
                return nums.length + 1;
            }   
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.