First Missing Positive


#1

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.


#2

Since the output is expected to be the smallest missing positive number, the value is expected to be between 0 and n. The below code will put the numbers from 0 to n in each of their respective places and finds out the missing number in the second pass. If we don’t find it, we return n+1.

class Solution {
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0) return 1;          //case: nums == null or nums == [], return 1
        for(int i = 0;i < nums.length;i++){                     //use nums array itself, the ideal array should be {1,2,3,4}
            int curr = nums[i];                                 //swap if nums[index] != index + 1;
            while(curr - 1 >= 0 && curr - 1 < nums.length && curr != nums[curr-1]){
                int next = nums[curr-1];
                nums[curr-1] = curr;
                curr = next;
            }
        }
        for(int i = 0;i< nums.length;i++){                      //check if nums[index] == index + 1;
            if(nums[i] != i+1) return i+1;
        }
        return nums.length+1;                                   //corner case: {1,2,3,4} return 5
    }
}