First Missing Positive

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.

The idea here is try to move A[i] to A[A[i]-1], assume we want to convert array from [3,2,1,4,0] -> [1,2,3,4,0]

so the first element in the array is not equal to i+1 is the missing positive.

public int firstMissingPositive(int[] A) {
        if (A==null||A.length==0) {
            return 1;
        } 

        for (int i=0; i<A.length; i++) {
            int index = A[i];
            //[3,2,1,4,0] -> [1,2,3,4,0]
            //1. Move A[i] to A[A[i]-1]
            //2. if not valid skip  
            if (index>0&&index<A.length&&i+1!=A[i]&&index!=A[index-1]) {
                swap(A, i, index-1);  
                i = i - 1;
            }
        }

        for (int i=0; i<A.length; i++) {
            if (i!=A[i]-1) {
                return i+1;
            }
        }
        return A.length+1;
    }

    private void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }