First Missing Positive - Leetcode

firstMissingPositive.java

/*
Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

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

public class Solution {
    public int firstMissingPositive(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        // ========= Time complexity: O(n) =========//
        int i = 0;
        while(i < A.length) {
            if(A[i] != i+1) {
                if(0 <= A[i]-1 && A[i]-1 < A.length) {
                    int tmp = A[A[i]-1];
                    if(tmp != A[i]) {
                        A[A[i]-1] = A[i];
                        A[i] = tmp;
                    } else {
                        // deal with this case: [2,2]
                        i++;
                    }
                } else {
                    // deal with this case: [0,1] or [3,1]
                    i++;
                }
            } else {
                // deal with case when A[i] == i+1, like [1,2]
                i++;
            }
        }
        
        int j = 0;
        for(; j < A.length; j++) {
            if(A[j] != j+1) return j+1;
        }
        
        return j+1;
        
        // ========= Time complexity: O(n*log(n)) =======//
        
        if(A.length == 0) return 1;
        Arrays.sort(A); // sort the array
        int idx = 0;
        int offset = 0;
        while(offset < A.length && A[offset] <= 0) {
            // check the offset to find the starting point
            offset++;
        }
        int i = 1;
        for(; offset < A.length; offset++) {
            if(offset > 0 && A[offset] == A[offset-1]) continue;
            if(A[offset] != i) break; // if it does not follow the rule when it is not increased by 1.
            i++;
        }
        
        return i;
    }
}